#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const double EPS=1.0e-10; #define ZEROP(x) (abs(x) xy; typedef pair lineseg; typedef vector vlinesegs; double inner_product(xy p1, xy p2) { return real(conj(p1)*p2); } double outer_product(xy p1, xy p2) { return imag(conj(p1)*p2); } int ccw_n(xy p1, xy p2, xy p3) { p2-=p1; p3-=p1; double op=outer_product(p2,p3); if ( LT(0,op) ) { return 1; } if ( LT(op,0) ) { return-1; } //if ( LT(inner_product(p2,p3),0) ) {return +2;} //if ( LT(norm(p2),norm(p3)) ) {return -2;} return 0; } bool cross_lines_notouched(xy p1, xy p2, xy q1, xy q2) { return ccw_n(p1,p2,q1)*ccw_n(p1,p2,q2)<0 && ccw_n(q1,q2,p1)*ccw_n(q1,q2,p2)<0; } bool cross_lines(const lineseg &l1, const lineseg &l2) { return cross_lines_notouched(l1.first, l1.second, l2.first, l2.second); } int ccw_t(xy p1, xy p2, xy p3) { p2-=p1; p3-=p1; double op=outer_product(p2,p3); if ( LT(0,op) ) { return 1; } if ( LT(op,0) ) { return-1; } if ( LT(inner_product(p2,p3),0) ) {return +2;} if ( LT(norm(p2),norm(p3)) ) {return -2;} return 0; } bool cross_lines_touch(xy p1, xy p2, xy q1, xy q2) { return ccw_t(p1,p2,q1)*ccw_t(p1,p2,q2)<=0 && ccw_t(q1,q2,p1)*ccw_t(q1,q2,p2)<=0; } /* intersection of lines o1+t*l1 and o2+s*l2 */ /* o1 +t*l1 = o2+s*l2. ( l1x l2x) ( t) ( l1y l2y) (-s) = o2-o1. ( t) __1___( l2y -l2x ) ((o2-o1)x) (-s) = det (-l1y l1x ) ((o2-o1)y) t=outer_product(o12,l2)/det s=outer_product(o12,l1)/det */ double crossing_length(xy o1, xy l1, xy o2, xy l2) { double det=outer_product(l1,l2); assert(!ZEROP(det)); return outer_product(o2-o1,l2)/det; } double crossing_length(lineseg l1, lineseg l2) { return crossing_length(l1.first, l1.second-l1.first, l2.first, l2.second-l2.first); } // 0: reference implementation // 1: data verification // 2: random data generator // 3: geometry generator // 4: origin map generator // #define MODE_REFERENCE 0 #define MODE_VERIFICATION 1 #define MODE_RANDOM_DATA 2 #define MODE_GEOMETRY 3 #define MODE_ORIGINMAP 4 #ifndef MODE #define MODE MODE_REFERENCE #endif #if MODE==MODE_REFERENCE #define mainReference main #elif MODE==MODE_VERIFICATION #define mainVerification main #elif MODE==MODE_RANDOM_DATA #define mainRandomData main #elif MODE==MODE_GEOMETRY #define mainGeometry main #elif MODE==MODE_ORIGINMAP #define mainOriginMap main #endif struct Mirror{ lineseg m; xy vec; Mirror(const lineseg &ls) :m(ls), vec(ls.second-ls.first){} xy turn(const xy& p) const { return conj((p-m.first)/vec)*vec+m.first; } lineseg turn(const lineseg &ls) const { return lineseg(turn(ls.first),turn(ls.second)); } Mirror turn(const Mirror &m2) const { return Mirror(turn(m2.m)); } }; typedef pair illusion_t; struct Illusions{ vector mirrors; vector myself; Illusions() :mirrors(2){} }; struct GeometryCollector{ public: GeometryCollector(Illusions &impl) :pimpl(&impl){} void collectMirror(const lineseg &ls, int i){ pimpl->mirrors[i].push_back(ls); } void collectPoint(const xy &cur,bool visible, int hardness){ pimpl->myself.push_back(illusion_t(cur,visible)); } Illusions *pimpl; }; struct DummyCollector{ public: DummyCollector(){} void collectMirror(const lineseg &ls, int i) {} void collectPoint(const xy &cur, bool visible, int hardness){} }; template int solve_half(const Mirror &m1, const Mirror &m2, const xy &orig, C &res) { lineseg ls_z(m2.m); vlinesegs ls; int ret=0; int cant_see = 0; xy first_illusion(m1.turn(orig)); if ( ZEROP(outer_product(m1.vec, orig-m1.m.first)) ) return 0; xy prev(orig); for ( int i=0 ; ; ++i ) { if ( i==0 ) ls.push_back(m1.m); else if ( i==1 ) ls.push_back(m1.turn(m2.m)); else { Mirror cm(ls.back()); ls.push_back(cm.turn(ls[ls.size()-2])); } if ( i>0 ) res.collectMirror(ls.back(),i&1); Mirror lastMirror(ls.back()); xy cur=lastMirror.turn(prev); prev=cur; lineseg los(orig,cur); bool visible=true; double len=0.0; if ( cross_lines(los,ls_z) ) len = crossing_length(los,ls_z); else len=1.0; if ( !cross_lines(los, ls.front()) ) visible=false; else if ( LT(crossing_length(los, ls.front()),len) ) len=crossing_length(los, ls.front()); else { visible=false; break; // is it OK? } for ( vlinesegs::iterator it=ls.begin() ; ++it!=ls.end() && visible ; ) { if ( !cross_lines(*it,los) ) { visible=false; } else { double clen = crossing_length(los,*it); if ( LT(len,clen) ) len=clen; else visible=false; } } res.collectPoint(cur,visible,cant_see); //.myself.push_back(illusion_t(cur,visible)); if ( visible ) { ret++; cant_see=0; if ( ret>=ILLUSION_MAX ) break; } else { ++cant_see; if ( (i&1)==0 && i>0) { int direction = ccw_n(orig,cur,first_illusion); bool endo=false; if ( direction==0 ) { /*if ( cross_lines(los,ls_z) ) endo=true; for ( vlinesegs::iterator it=ls.begin() ; it!=ls.end() && !endo ; ++it ) if(ccw_n(orig,cur,it->first) ==ccw_n(orig,cur,it->second)) endo=true; */ endo=true; } for ( vlinesegs::iterator it=ls.begin() ; it!=ls.end() && !endo ; ++it ) { if(ccw_n(orig,cur,it->first)==direction && ccw_n(orig,cur,it->second)==direction) endo=true; } if ( endo ) break; } } //cout<=ILLUSION_MAX?ILLUSION_MAX:ret; } }; namespace std{ template basic_ostream& operator<<(basic_ostream &o, const xy &p) { o< OUT& operator<<(OUT &o, const lineseg &ls){ o<(out,"\n")); out< p(9); int rmin=ILLUSION_MAX, rmax=0; SolverNormal solve; if ( xyonlineseg(orig,m1.m) || xyonlineseg(orig,m2.m) ) return false; do{ //copy(p.begin(),p.end(),ostream_iterator(cout,"")); //cout<::iterator it; for ( it=p.begin() ; it!=p.end() && *it==2 ; ++it ) *it=0; ++(*it); } } while ( p.back()==0 ); res=rmin; return true; } struct SolverVerify{ int operator()(const Mirror &m1, const Mirror &m2, const xy &orig) const{ assert(!cross_lines(m1.m, m2.m)); int res; if ( !check_stability(m1,m2,orig,res) ) { cout<<"Error! no stability"< ixy; typedef pair ilineseg; const int imax; double left, bottom, width; xy xyFromIxy(const ixy &p) { return xy(left + width*p.first/imax, bottom+width*p.second/imax); } int queryMap(map &geom, const ixy &iorig, const Mirror &m1, const Mirror &m2 ){ if ( geom.count(iorig)==0 ) { xy orig(xyFromIxy(iorig)); cout<<"\t("< geom; queue toBeProcessed; static int fileno = 0; ++fileno; const int sep=16; //This must be 2^n const int s30= imax/sep; for ( int i=0 ; i0 ) { ixy i1=toBeProcessed.front().first; ixy i3=toBeProcessed.front().second; toBeProcessed.pop(); { xy p(xyFromIxy(i1)),q(xyFromIxy(i3)); cout<>1, (i1.second+i3.second)>>1); ixy il(i1.first, ic.second); ixy ir(i3.first, ic.second); ixy ib(ic.first, i1.second); ixy it(ic.first, i2.second); toBeProcessed.push(ilineseg(i1,ic)); toBeProcessed.push(ilineseg(ib,ir)); toBeProcessed.push(ilineseg(il,it)); toBeProcessed.push(ilineseg(ic,i3)); } } ostringstream oss; oss<<"origmap-"<::const_iterator it=geom.begin() ; it!=geom.end() ; ++it ){ xy p(xyFromIxy(it->first)); out<second< struct NormalDataOperator { int operator()(void) const { double cx,cy; Solver solve; while ( cin>>cx>>cy && !(ZEROP(cx)&&ZEROP(cy))) { xy cur(cx,cy); double m1x1, m1y1, m1x2, m1y2; double m2x1, m2y1, m2x2, m2y2; cin >> m1x1>>m1y1>>m1x2>>m1y2; cin >> m2x1>>m2y1>>m2x2>>m2y2; lineseg m1(xy(m1x1,m1y1),xy(m1x2,m1y2)); lineseg m2(xy(m2x1,m2y1),xy(m2x2,m2y2)); int ans; ans=solve(Mirror(m1),Mirror(m2),cur); if ( ans>=ILLUSION_MAX ) cout<<"TOO MANY"< n; return n(); } int mainVerification() { NormalDataOperator n; return n(); } int mainGeometry() { NormalDataOperator n; return n(); } int mainOriginMap() { NormalDataOperator n; return n(); } struct RandomDataGenerator{ int rnd(){ for(;;) { int r=rand()/(RAND_MAX/50)+1; if ( r<=50 ) return r; } } void genLines(int *d) { for(;;){ for ( int i=0 ; i<8 ; ++i ) d[i]=rnd(); xy p1(d[0],d[1]),p2(d[2],d[3]); xy q1(d[4],d[5]),q2(d[6],d[7]); if(!cross_lines_touch(p1,p2,q1,q2)) return; } } int genOrigin(int *orig, const int *d){ for(;;) { orig[0]=rnd(); orig[1]=rnd(); xy cur(orig[0],orig[1]); xy p1(d[0],d[1]),p2(d[2],d[3]); xy q1(d[4],d[5]),q2(d[6],d[7]); int res; if(!xyonlineseg(cur,lineseg(p1,p2)) && !xyonlineseg(cur,lineseg(q1,q2)) && check_stability(Mirror(lineseg(p1,p2)), Mirror(lineseg(q1,q2)), cur,res)){ return res; } } } int operator()(){ srand(time(0)); vector d(10); vector occupied(101,0); for ( int i=0 ; i<100 ; ++i ) { genLines(&d[2]); int nrec=1000; int rrec=0; vector e(2); for ( int i=0 ; i<10 ; ++i ) { int res=genOrigin(&e[0],&d[2]); int n = occupied[res]; if ( n