#include using namespace std; typedef long long int ll; typedef long double ld; #define EPS (1e-10) #define EQ(a,b) (fabs(a-b) <= fabs(a+b) * EPS) /** * ICPC Central Europe Regional Contest 2018 * Sample solution: Mirrority Report * * @author Vaclav Blazej */ // list all combinations of c elements in n // ex for c=3,n=5: [0 1 2],[0 1 3],[0 1 4],[1 2 3], ... vector> all_combinations(ll c, ll n){ vector> res; vector permutation(c); for(int i=0; i=val-cnt){ ++cnt; --idx; } if(cnt==c)break; permutation[idx]++; while(++idx()); return res; } struct Pt{ ld x,y; Pt operator-(){return{-x,-y};} Pt operator+(const Pt&p){return{x+p.x,y+p.y};} Pt operator-(const Pt&p){return{x-p.x,y-p.y};} Pt operator*(ld d){return {x*d,y*d};} Pt operator/(ld d){return {x/d,y/d};} friend ostream &operator<<(ostream &os, const Pt&a){ os<>(istream &is, Pt&a){ is>>a.x>>a.y; return is; } }; struct Line{ Pt a,b; ll time,id; friend ostream &operator<<(ostream &os, const Line&a){ os< a; ld cross(Pt a, Pt b){ return a.x*b.y-a.y*b.x; } ld cross(Pt a, Pt b, Pt c){ return cross(b-a,c-a); } ld dot(Pt a, Pt b){ return a.x*b.x+a.y*b.y; } ld norm(Pt a){ return sqrt(dot(a,a)); } ld line_point_dist(Line l, Pt p){ return fabs(cross(p-l.a,l.b-l.a)/norm(l.b-l.a)); } Pt lines_intersection(Line p,Line q){ Pt v=p.b-p.a; Pt w=q.b-q.a; ld t=cross(w,p.a-q.a)/cross(v,w); return p.a+v*t; } bool have_intersection(Line p,Line q){ Pt v=p.b-p.a; Pt w=q.b-q.a; ld t=cross(v,w); return abs(t)>EPS; } void mirror(Pt &what, Line by){ ld dist=line_point_dist(by,what); Pt d=by.b-by.a; d={d.y,-d.x}; if(dot(d,what-by.a)>0)d=-d; d=d*dist/norm(d); what=what+d*2; } void mirror(Line &what, Line by){ mirror(what.a,by); mirror(what.b,by); } int main(){ ll N;cin>>N; a=vector(N); cin>>s.x>>s.y>>e.x>>e.y; for(int i=0; i>a[i].a>>a[i].b; } vector directions; vector> resultPermutations; for(int c=0;c<=N;++c){ auto r=all_combinations(c,N); for(vector p:r)do{ Pt ee=e; vector copy(a.begin(),a.end()); vector done(N,false); vector presentLines; map> forbiddenTimePoints; ll idx=0; while(true){ for(int i=0; i=p.size())break; for(int i=0; i intersections(presentLines.size()); vector parallel(presentLines.size(),0); for(int i=0; i> distance(presentLines.size()); ld goalDistance = norm(dir.b-dir.a); for(int i=0; i0){ distance[i].first=norm(intersections[i]-dir.a); }else{ distance[i].first=-1; // never crosses } distance[i].second=i; } sort(distance.begin(),distance.end()); ll time=0; bool good=1; for(int i=0; igoalDistance){ break; } ll j=distance[i].second; if(presentLines[j].time==time){ if(time < p.size() && presentLines[j].id==p[time]){ Pt currentInterection = lines_intersection(presentLines[j],dir); for(Pt p:forbiddenTimePoints[time]){ if(norm(p-currentInterection) < 1e-4){ good=0; break; } } time++; }else{ good=0; break; } } } if(good && time==p.size()){ ld d=atan2(dir.b.y-dir.a.y,dir.b.x-dir.a.x); directions.push_back(d); resultPermutations.push_back(p); } }while(next_permutation(p.begin(),p.end())); } vector unique(directions.size(),true); for(int i=0; i #ifdef PAINT cerr<<"settings.outformat=\"pdf\";\n"; cerr<<"unitsize(0.2cm);\n"; cerr<<"real r = 1.5;\n"; cerr<<"fill(circle(("< permutation=resultPermutations[i]; Pt last=s,cur; cerr<<"pen blue=rgb(0,0,255);\n"; blue=min(255ll,blue+(ll)(255/directions.size())); for(int j=0; j