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 

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


#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) < -eps)return RIGHT;
  else if(cross(a,b)>eps)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));
      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;
    }
  }
  return false;
}

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()){
    //if (flag && fabs(cross(in1[(i+1)%in1.size()]-in1[i],a-in1[i])) < eps && 
    //    	fabs(cross(in1[(i+1)%in1.size()]-in1[i],b-in1[i])) < eps)continue;
    rep(j,in2.size()){
      //      if (flag && fabs(cross(in2[(j+1)%in2.size()]-in2[j],a-in1[j])) < eps && 
      //	  fabs(cross(in2[(j+1)%in2.size()]-in2[j],b-in1[j])) < eps)continue;
    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){
  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);

    rep(i,n){
      if (i == now)continue;
      if (adj[now][i]){
	if(have_same_line(in[now].newp,in[i].ori,a,b,false)&&
	   is_intersected_polygon(in[i].ori,in[now].newp))Q.push(i);
      }else if (up[i][now]){
	if (is_intersected_polygon(in[i].ori,in[now].newp))Q.push(i);
      }
    }
  }

  int m = n;
  rep(i,n){
    in[i].oriid=i;
    if (in[i].newp.size() != 0)in[i].newid=m++;
    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;
      adj[myori][mynew]=adj[mynew][myori]=true;
    }

    rep(j,n){
      if (i == j)continue;
      int yourori=in[j].oriid,yournew=in[j].newid;
      bool tmp = up[i][j];
      //in[i].ori-in[j].ori
      bool adj_myori_yourori=adj[myori][yourori];

      up[myori][yourori]=up[myori][yourori];
      if (adj_myori_yourori && have_same_line(in[i].ori,in[j].ori,a,b,true))
	adj[myori][yourori]=true;
      else adj[myori][yourori]=false;

      //in[i].ori-in[j].newp
      if (yournew != -1){
	if (up[myori][yourori])up[myori][yournew]=false;
	else                   up[myori][yournew]=true;
	adj[myori][yournew]=false;
      }
      
      //in[i].newp-in[j].ori
      if (mynew != -1){
	up[mynew][yourori]=true;
	adj[mynew][yourori]=false;
      }
      
      //in[i].newp-in[j].ori
      if (mynew != -1 && yournew != -1){
	up[mynew][yournew]=tmp?false:true;
	if (adj_myori_yourori && have_same_line(in[i].newp,in[j].newp,a,b,true))adj[mynew][yournew]=true;
	else adj[mynew][yournew]=false;
      }
    }
  }

  rep(i,n){
    if (in[i].newp.size() != 0){
      in[in[i].newid].ori=in[i].newp;
      in[i].newp.clear();
    }
  }

  n = m;
}

void output(int n,Polygon in[N]){
  cout <<"output begin" << endl;
  rep(i,n){
    if (in[i].ori.size() == 0)continue;
    cout << i <<endl;
    cout <<"[";
    rep(j,in[i].ori.size()+1)cout << in[i].ori[j%in[i].ori.size()]<<",";
    cout <<"],";
    cout << endl;
  }
  cout << endl;
  
  cout << "up"<<endl;
  rep(i,n){
    rep(j,n)cout << up[i][j];
    cout << endl;
  }
  cout << endl;
  
  cout << "adj " << endl;
  rep(i,n){
    rep(j,n)cout << adj[i][j];
    cout <<endl;
  }
  cout << endl;
    

  cout <<"output end" << endl<<endl;
}
	     
int solve(int querry){
  int n=1;
  Polygon in[N];
  // initialization
  rep(i,N)in[i].ori.clear(),in[i].newp.clear();
  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));

  bool isend=false;
  rep(i,querry){
    P p,q;
    cin>>p.real()>>p.imag()>>q.real()>>q.imag();
    pair<P,P> line = make_line(p,q);
    //cout << p<<q<<endl;
    //    cout << line.first <<" " << line.second << endl;
    int index = find_most_upper(n,in,p);
    if (index == -1||isend){
      //isend=true;
      exit(1);
      continue;
    }
    origami(n,index,in,line.first,line.second);
    //        output(n,in);
  }

  
  int cnt=0;
  P hole;
  cin>>hole.real()>>hole.imag();
  rep(i,n){
    if (is_in(in[i].ori,hole))cnt++;
  }
  //  cout << "number of paper " << n << endl;
  
  //    output(n,in);
  return cnt;
}

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

Compiler output:
a.cc: In function 'std::pair<std::complex<double>, std::complex<double> > make_line(P, P)':
a.cc:79:11: error: lvalue required as left operand of assignment
   79 |   tmp.real()/=2;tmp.imag()/=2;
      |   ~~~~~~~~^~
a.cc:79:25: error: lvalue required as left operand of assignment
   79 |   tmp.real()/=2;tmp.imag()/=2;
      |                 ~~~~~~~~^~
a.cc:81:7: error: no matching function for call to 'swap(double, double)'
   81 |   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:81:27: error: cannot bind non-const lvalue reference of type 'double&' to an rvalue of type 'double'
   81 |   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:81:7: note:   mismatched types 'std::__cxx11::basic_stringbuf<_CharT, _Traits, _Alloc>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::__cxx11::basic_istringstream<_CharT, _Traits, _Allocator>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::__cxx11::basic_ostringstream<_CharT, _Traits, _Allocator>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::__cxx11::basic_stringstream<_CharT, _Traits, _Allocator>' and 'double'
   81 |   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:81:7: note:   mismatched types '_Tp [_Nm]' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::pair<_T1, _T2>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::pair<_T1, _T2>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::tuple<_UTypes ...>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::tuple<_UTypes ...>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::deque<_Tp, _Alloc>' and 'double'
   81 |   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:81:7: note:   mismatched types 'std::vector<_Tp, _Alloc>' and 'double'
   81 |   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_queue.h:445:5: note:   template argument deduction/substitution failed:
a.cc:81:7: note:   mismatched types 'std::queue<_Tp, _Seq>' and 'double'
   81 |   swap(ret.real(),ret.imag());
      |   ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:834:5: note: candidate: 'template<class _Tp, class _Sequence, class _Compare> typename std::enable_if<std::_