Language: C++

#include<iostream>
#include<queue>
#include<vector>
#include<complex>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define pb         push_back
const double eps = 1e-10;

const int N = 2000;

typedef complex<double> P;

bool adj[N][N];
bool up[N][N];//up[i][j] = 1 i >=j 
bool cpyadj[N][N];
bool cpyup[N][N];

class Polygon{
public:
  vector<P> ori,newp;
  int oriid,newid;
  int cutbit;
  vector<P> inipos;
};

void outputpolygon(vector<P> &a){
  cout << "[";
  rep(i,a.size()+1)cout << a[(i+1)%a.size()]<<",";
  cout << "],"<<endl;
}


#define RIGHT 1
#define LEFT -1

double cross(P a,P b){
  return a.real()*b.imag()-a.imag()*b.real();
}

double dot(P a,P b){
  return a.real()*b.real()+a.imag()*b.imag();
}

bool isp(P &a,P &b,P &c){
  return abs(a-c)+abs(b-c) < abs(a-b) + eps;
}

P intersection_ll(P &a1,P &a2,P &b1,P &b2){
  P a=a2-a1,b=b2-b1;
  return a1+ a*cross(b,b1-a1)/cross(b,a);
}

int ccw(P a,P b){
  if (cross(a,b)    < -0)return RIGHT;
  else if(cross(a,b)>  0)return LEFT;
  return 2;
}

bool is_intersected_ls(P &a1,P &a2,P &b1,P &b2){
  if (isp(a1,a2,b1)||isp(a1,a2,b2)||isp(b1,b2,a1)||
      isp(b1,b2,a2))return true;
  if (cross(a2-a1,b1-a1)*cross(a2-a1,b2-a1)<-eps &&
      cross(b2-b1,a1-b1)*cross(b2-b1,a2-b1)<-eps)
    return true;
  return false;
}

//LEFT remain,RIGHT reflect
void Convex_cut(vector<P> in,P &a1,P &a2,
		vector<P> &ori,vector<P> &newp){
  int n = in.size();
  ori.clear();newp.clear();
  rep(i,n){
    P now = in[i],next=in[(i+1)%n];
    if( ccw(a1-a2,now-a2) == LEFT)ori.pb(now);
    else if( ccw(a1-a2,now-a2) == RIGHT)newp.pb(now);
    if (ccw(a1-a2,now-a2)*ccw(a1-a2,next-a2)<0){
      //ori.pb(intersection_ll(a1,a2,now,next));
      ori.pb(intersection_ll(now,next,a1,a2);
      newp.pb(intersection_ll(a1,a2,now,next));
    }
  }
}

pair<P,P> make_line(P p,P q){
  int cutpos=RIGHT;
  P tmp=(p+q);
  tmp.real()/=2;tmp.imag()/=2;
  P ret=q-tmp;
  swap(ret.real(),ret.imag());
  ret.real()*=-1;
  if ( ccw(ret,p-tmp) != cutpos)return make_pair(tmp,ret+tmp);
  return make_pair(ret+tmp,tmp);
}

bool is_in(vector<P> &in,P &a){
  int cnt=0;
  int n = in.size();
  rep(i,n){
    P cur = in[i]-a,next=in[(i+1)%n]-a;
    if (cur.imag()>next.imag())swap(cur,next);
    if (cur.imag()<0&&0<=next.imag()&&
	cross(next,cur)>= 0)cnt++;
    if (isp(in[i],in[(i+1)%n],a))return true;
  }

  if (cnt%2 == 1)return true;
  return false;
}

P reflect(P &o,P &p,P &q){
  P N=p-o,L=q-o;
  double t = abs(L);
  N/=abs(N);
  L/=abs(L);
  double prepL = dot(N,L);//theta element of vector L against N (|L|=|N|=1
  double d=2*prepL;
  P r(d*N - L);//R vector symmetric point of L
  return o+t*r;
}

int find_most_upper(int n,Polygon *in,P &p){
  int index = -1;
  rep(i,n){
    if (is_in(in[i].ori,p)){
      if (index == -1)index =i;
      else if (up[i][index])index=i;
    }
  }
  return index;
}

//a ori,b newp
bool is_intersected_polygon(vector<P> &a,vector<P> &b){
  rep(i,a.size()){
    if (is_in(b,a[i]))return true;
    rep(j,b.size()){
      if (is_intersected_ls(a[i],a[(i+1)%a.size()],
			    b[j],b[(j+1)%b.size()])){
	return true;
      }
    }
  }
  rep(j,b.size())if (is_in(a,b[j]))return true;
  return false;
}


double distance_l_p(P a,P b,P c){
  return abs( cross(b-a,c-a))/abs(b-a);
}

bool issame(P &a,P &b){
  return fabs(a.real()-b.real())<eps && fabs(a.imag()-b.imag())<eps;
}

bool have_same_line(vector<P> &in1,vector<P> &in2,P &a,P &b,bool flag){
  rep(i,in1.size()){
    rep(j,in2.size()){
      if (isp(in1[i],in1[(i+1)%in1.size()],in2[j])
	  ||isp(in1[i],in1[(i+1)%in1.size()],in2[(j+1)%in2.size()])
	  )return true;

      if ((issame(in1[i],in2[j])&&issame(in1[(i+1)%in1.size()],in2[(j+1)%in2.size()]))
	||
	(issame(in1[i],in2[(j+1)%in2.size()])&&issame(in1[(i+1)%in1.size()],in2[j]))
	)return true;
    }
  }
  return false;
}

bool vis[N];
void origami(int &n,int ini,Polygon in[N],P &a,P &b,
	     pair<P,P> *line,int querry){
  int m = n;
  vector<P> dummy;
  rep(i,N){
    in[i].newp.clear(),in[i].newid=-1;//nen no tame
  }

  rep(i,N)vis[i]=false;
  queue<int> Q;
  Q.push(ini);
  while(!Q.empty()){
    int now = Q.front();Q.pop();
    if (vis[now])continue;
    
    vis[now]=true;

    Convex_cut(in[now].ori,a,b,in[now].ori,in[now].newp);
    if (in[now].newp.size() != 0){
      in[now].oriid=now;
      in[now].newid=m++;
      in[in[now].newid].cutbit=in[now].cutbit|(1<<querry);
    }
    
    
    in[now].inipos=in[now].newp;
    for(int j=querry-1;j>=0;j--){
      if((in[now].cutbit&(1<<j)) != 0){
	rep(k,in[now].inipos.size()){
	  in[now].inipos[k]=reflect(line[j].first,line[j].second,in[now].inipos[k]);
	}
      }
    }
    
    
    rep(i,n){
      if (i == now)continue;
      if (adj[now][i]){
	if(have_same_line(in[now].inipos,in[i].inipos,a,b,false))
	  Q.push(i);
      }
      if (up[i][now]){
	if (is_intersected_polygon(in[now].newp,in[i].ori))
	  Q.push(i);
      }
    }
  }
  
  rep(i,n){
    rep(j,in[i].newp.size()){
      in[i].newp[j]=reflect(a,b,in[i].newp[j]);
    }
  }
  

  rep(i,n){
    int myori=in[i].oriid,mynew=in[i].newid;
    if (in[i].newp.size() == 0)mynew=-1;
    
    if (mynew != -1){
      up[myori][mynew]=false;
      up[mynew][myori]=true;
    }
    
    rep(j,n){
      if (i == j)continue;
      int yori=in[j].oriid,yournew=in[j].newid;
      bool tmp = up[i][j];
      //in[i].ori-in[j].ori
      up[myori][yori]=up[myori][yori];

      //in[i].ori-in[j].newp
      if (yournew != -1){
	up[myori][yournew]=false;
      }

      //in[i].newp-in[j].ori
      if (mynew != -1){
	if (is_intersected_polygon(in[i].newp,in[j].ori)){
	  up[mynew][yori]=true;
	}else {
	  up[mynew][yori]=false;
	}
      }
 
      //in[i].newp-in[j].ori
      if (mynew != -1 && yournew != -1){
	if (up[yori][myori] && is_intersected_polygon(in[i].newp,in[j].newp))
	  up[mynew][yournew]=true;
	else up[mynew][yournew]=false;
      }
    }
  }
        
    
    
  rep(i,n){
    if (in[i].newp.size() != 0){
      in[in[i].newid].ori=in[i].newp;
      in[in[i].newid].oriid=in[i].newid;
      in[i].newp.clear();
    }
  }

  n = m;

  rep(i,m){
    in[i].inipos.clear();
    in[i].inipos=in[i].ori;
    for(int j=querry;j>=0;j--){
      if((in[i].cutbit&(1<<j)) != 0){
	rep(k,in[i].inipos.size()){
	  in[i].inipos[k]=reflect(line[j].first,line[j].second,in[i].inipos[k]);
	}
      }
    }
  }

  rep(i,m){
    REP(j,i+1,m){
      if (have_same_line(in[i].inipos,in[j].inipos,a,b,true)){
	adj[i][j]=adj[j][i]=true;
      }else adj[i][j]=adj[j][i]=false;
    }
  }
}
	     
int solve(int querry){
  int n=1;
  static Polygon in[N];
  pair<P,P> line[10];
  P pos[10];
  // initialization
  rep(i,N){
    in[i].ori.clear();
    in[i].newp.clear();
    in[i].inipos.clear();
    in[i].oriid=i;
    in[i].newid=-1;
    in[i].cutbit=0;
  }
  rep(i,N)rep(j,N)adj[i][j]=false,up[i][j]=false;
  
  in[0].ori.pb(P(0,0));
  in[0].ori.pb(P(0,100));
  in[0].ori.pb(P(100,100));
  in[0].ori.pb(P(100,0));
  in[0].inipos=in[0].ori;

  rep(i,querry){
    P p,q;
    cin>>p.real()>>p.imag()>>q.real()>>q.imag();
    pos[i]=p;
    pair<P,P> tmp;
    line[i] = make_line(p,q);
  }

  rep(i,querry){
    int index = find_most_upper(n,in,pos[i]);
    if (index == -1){
    }else origami(n,index,in,line[i].first,line[i].second,
		  line,i);
  }

  
  int cnt=0;
  P hole;
  cin>>hole.real()>>hole.imag();
  rep(i,n){
    if (in[i].ori.size() && is_in(in[i].ori,hole))cnt++;
  }

  return cnt;
}

main(){
  int q;
  while(cin>>q&&q){
    cout << solve(q) << endl; 
  }
}

Compiler output:
a.cc: In function 'void Convex_cut(std::vector<std::complex<double> >, P&, P&, std::vector<std::complex<double> >&, std::vector<std::complex<double> >&)':
a.cc:81:45: error: expected ')' before ';' token
   81 |       ori.pb(intersection_ll(now,next,a1,a2);
      |             ~                               ^
      |                                             )
a.cc: In function 'std::pair<std::complex<double>, std::complex<double> > make_line(P, P)':
a.cc:90:11: error: lvalue required as left operand of assignment
   90 |   tmp.real()/=2;tmp.imag()/=2;
      |   ~~~~~~~~^~
a.cc:90:25: error: lvalue required as left operand of assignment
   90 |   tmp.real()/=2;tmp.imag()/=2;
      |                 ~~~~~~~~^~
a.cc:92:7: error: no matching function for call to 'swap(double, double)'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/exception_ptr.h:41,
                 from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/move.h:226:5: note: candidate: 'std::_Require<std::__not_<std::__is_tuple_like<_Tp> >, std::is_move_constructible<_Tp>, std::is_move_assignable<_Tp> > std::swap(_Tp&, _Tp&) [with _Tp = double; _Require<__not_<__is_tuple_like<_Tp> >, is_move_constructible<_Tp>, is_move_assignable<_Tp> > = void]' (near match)
  226 |     swap(_Tp& __a, _Tp& __b)
      |     ^~~~
/usr/include/c++/14/bits/move.h:226:5: note:   conversion of argument 2 would be ill-formed:
a.cc:92:27: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
   92 |   swap(ret.real(),ret.imag());
      |                   ~~~~~~~~^~
/usr/include/c++/14/bits/exception_ptr.h:229:5: note: candidate: 'void std::__exception_ptr::swap(exception_ptr&, exception_ptr&)'
  229 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |     ^~~~
/usr/include/c++/14/bits/exception_ptr.h:229:25: note:   no known conversion for argument 1 from 'double' to 'std::__exception_ptr::exception_ptr&'
  229 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |          ~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/14/complex:45,
                 from a.cc:4:
/usr/include/c++/14/sstream:1204:5: note: candidate: 'template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_stringbuf<_CharT, _Traits, _Alloc>&, basic_stringbuf<_CharT, _Traits, _Alloc>&)'
 1204 |     swap(basic_stringbuf<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/14/sstream:1204:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::__cxx11::basic_stringbuf<_CharT, _Traits, _Alloc>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/sstream:1212:5: note: candidate: 'template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_istringstream<_CharT, _Traits, _Allocator>&, basic_istringstream<_CharT, _Traits, _Allocator>&)'
 1212 |     swap(basic_istringstream<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/14/sstream:1212:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::__cxx11::basic_istringstream<_CharT, _Traits, _Allocator>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/sstream:1219:5: note: candidate: 'template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_ostringstream<_CharT, _Traits, _Allocator>&, basic_ostringstream<_CharT, _Traits, _Allocator>&)'
 1219 |     swap(basic_ostringstream<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/14/sstream:1219:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::__cxx11::basic_ostringstream<_CharT, _Traits, _Allocator>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/sstream:1226:5: note: candidate: 'template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_stringstream<_CharT, _Traits, _Allocator>&, basic_stringstream<_CharT, _Traits, _Allocator>&)'
 1226 |     swap(basic_stringstream<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/14/sstream:1226:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::__cxx11::basic_stringstream<_CharT, _Traits, _Allocator>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/move.h:250:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> std::__enable_if_t<((bool)std::__is_swappable<_Tp>::value)> std::swap(_Tp (&)[_Nm], _Tp (&)[_Nm])'
  250 |     swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
      |     ^~~~
/usr/include/c++/14/bits/move.h:250:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types '_Tp [_Nm]' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44:
/usr/include/c++/14/bits/stl_pair.h:1089:5: note: candidate: 'template<class _T1, class _T2> typename std::enable_if<std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value>::type std::swap(pair<_T1, _T2>&, pair<_T1, _T2>&)'
 1089 |     swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_pair.h:1089:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::pair<_T1, _T2>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_pair.h:1106:5: note: candidate: 'template<class _T1, class _T2> typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type std::swap(pair<_T1, _T2>&, pair<_T1, _T2>&)' (deleted)
 1106 |     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;
      |     ^~~~
/usr/include/c++/14/bits/stl_pair.h:1106:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::pair<_T1, _T2>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:54:
/usr/include/c++/14/bits/basic_string.h:4039:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> void std::swap(__cxx11::basic_string<_CharT, _Traits, _Allocator>&, __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 4039 |     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~
/usr/include/c++/14/bits/basic_string.h:4039:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68:
/usr/include/c++/14/tuple:2805:5: note: candidate: 'template<class ... _Elements> typename std::enable_if<std::__and_<std::__is_swappable<_Elements>...>::value>::type std::swap(tuple<_UTypes ...>&, tuple<_UTypes ...>&)'
 2805 |     swap(tuple<_Elements...>& __x, tuple<_Elements...>& __y)
      |     ^~~~
/usr/include/c++/14/tuple:2805:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::tuple<_UTypes ...>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/tuple:2823:5: note: candidate: 'template<class ... _Elements> typename std::enable_if<(! std::__and_<std::__is_swappable<_Elements>...>::value)>::type std::swap(tuple<_UTypes ...>&, tuple<_UTypes ...>&)' (deleted)
 2823 |     swap(tuple<_Elements...>&, tuple<_Elements...>&) = delete;
      |     ^~~~
/usr/include/c++/14/tuple:2823:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::tuple<_UTypes ...>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/deque:66,
                 from /usr/include/c++/14/queue:62,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_deque.h:2370:5: note: candidate: 'template<class _Tp, class _Alloc> void std::swap(deque<_Tp, _Alloc>&, deque<_Tp, _Alloc>&)'
 2370 |     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_deque.h:2370:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::deque<_Tp, _Alloc>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/queue:63:
/usr/include/c++/14/bits/stl_vector.h:2122:5: note: candidate: 'template<class _Tp, class _Alloc> void std::swap(vector<_Tp, _Alloc>&, vector<_Tp, _Alloc>&)'
 2122 |     swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_vector.h:2122:5: note:   template argument deduction/substitution failed:
a.cc:92:7: note:   mismatched types 'std::vector<_Tp, _Alloc>' and 'double'
   92 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/queue:66:
/usr/include/c++/14/bits/stl_queue.h:445:5: note: candidate: 'template<class _Tp, class _Seq> typename std::enable_if<std::__is_swappable<_T2>::value>::type std::swap(queue<_Tp, _Seq>&, queue<_Tp, _Seq>&)'
  445 |     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
      |     ^~~~
/usr/include/c++/14/bits/stl_q