// schnelles auffinden von schnitten bei vielen strecken
#include <iostream>           // 2004 stefan reiss
#include <algorithm>          // www.reisz.de
#include <set>
#include <cmath>
using namespace std;

#define forint(i,a,b) for(int i=(a);i!=(b);++i)
struct point { double x,y; };
const int NPTS = 100000; point pts[NPTS]; int pti[NPTS];
int  found1 = -1 , found2 = -1;

/* p0->p1->p2   +1=counter clockw;  -1=clockwise; 0=p2 between p01*/
int ccw (point p0 , point p1 , point p2)
{ point d1 , d2; 
  d1.x=p1.x-p0.x; d1.y=p1.y-p0.y; d2.x=p2.x-p0.x; d2.y=p2.y-p0.y;
  if (d1.x * d2.y > d1.y * d2.x)  return +1;
  if (d1.x * d2.y < d1.y * d2.x)  return -1;
  if (d1.x * d2.x < 0 || d1.y * d2.y < 0) return -1;
  if (d1.x * d1.x + d1.y * d1.y <
      d2.x * d2.x + d2.y * d2.y)  return +1;
  return 0;
}

// p0 and p1 of the lines are ordered so that lessY()(p0,p1) == true
bool lineleft (point * la , point * lb)
{ int ori[4];
  ori[0]= ccw (lb[0],lb[1],la[0]);  ori[1]= ccw (lb[0],lb[1],la[1]);
  ori[2]= ccw (la[0],la[1],lb[0]);  ori[3]= ccw (la[0],la[1],lb[1]);
  if (ori[0] == ori[1]) return ori[0] == 1;  // left or right
  if (ori[2] == ori[3]) return ori[2] == -1; // left or right
  found1 = la-pts; found2 = lb-pts; return false; // intersecting;
}

bool ptilow(int a , int b) { return  pts[a].y < pts[b].y; }
struct lls { bool operator() (int a, int b) const
{ return lineleft(pts+a,pts+b);}};

void main()
{ forint(t,0,NPTS) { pts[t].x = sin(t/2)*t; pts[t].y=cos(t/2)*t; }
  pts[50].x = 0; pts[50].y = 1; pts[51].x = 1; pts[51].y = 0; 
  set<int,lls> s; set<int,lls>::iterator si,si1,si2;
  forint(j,0,NPTS/2) if(ptilow(2*j+1,2*j)) swap(pts[2*j],pts[2*j+1]);
  forint(i,0,NPTS) pti[i] = i; sort(pti,pti+NPTS,ptilow);
  forint(k,0,NPTS)
  { if(pti[k]%2 == 0) s.insert(pti[k]); 
    else
    { si1 = si2 = si = s.find(pti[k]-1); 
      if(si1 != s.begin() && ++si2 != s.end())
      { if (!s.key_comp() (*--si1 , *si2)) 
        {cout << "switch\n"; found1=*si1; found2=*si2; }}
      s.erase(si);
    } if(found1 != -1) { cout<<found1<<","<<found2<<"\n"; break; }
  } 
  if(found1!=-1) cout << pts[found1].x<<","<<pts[found1].y<<"-"<<
                       pts[found1+1].x<<","<<pts[found1+1].y<<"\n";
  if(found2!=-1) cout << pts[found2].x  <<","<<pts[found2].y  <<"-"<<
                       pts[found2+1].x<<","<<pts[found2+1].y<<"\n";
  cout << "done" << endl; cin.get();
}