#include <LEDA/plane_alg.h>


random_source& operator>>(random_source& R, point& p)
{ double x,y;
  R >> x >>y;
  p = point(x,y);
  return R;
}


main()
{
   int N = read_int("N = ");

   list<point>     L;
   list<rat_point> L1;
   random_source ran(0,100000);

   ran.set_seed(12345*N);

   for(int i=0; i<N; i++) 
   { int x,y;
     ran >> x >> y;
     L.append(point(x,y));
     L1.append(rat_point(x,y));
    }


  // flipping with floating point points

  GRAPH<point,int>  D1;
  GRAPH<circle,point> V1;

  list<edge> d_list;

  float T, t1, t2, t3;

/*
  cout << "DELAUNAY FLIP0(float) " << flush;
  T = used_time();
  TRIANGULATE_POINTS(L,D1);
  t1 = used_time(T);
  DELAUNAY_FLIPPING(D1);
  t2 = used_time(T);
  DELAUNAY_TO_VORONOI_OLD(D1,V1);
  t3 = used_time(T);
  cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
          V1.number_of_nodes(), V1.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
*/


  cout << "DELAUNAY FLIP(float)  " << flush;
  T = used_time();
  TRIANGULATE_POINTS(L,D1);
  t1 = used_time(T);
  DELAUNAY_FLIPPING(D1,d_list);
  t2 = used_time(T);
  DELAUNAY_TO_VORONOI(D1,V1);
  t3 = used_time(T);
  cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
          V1.number_of_nodes(), V1.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;

  // flipping with rational points

  GRAPH<rat_point,int> D2;
  GRAPH<rat_circle,rat_point> V2;

/*
  cout << "DELAUNAY FLIP0(exact) " << flush;
  T = used_time();
  TRIANGULATE_POINTS(L1,D2);
  t1 = used_time(T);
  DELAUNAY_FLIPPING(D2);
  t2 = used_time(T);
  DELAUNAY_TO_VORONOI_OLD(D2,V2);
  t3 = used_time(T);
  cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
          V2.number_of_nodes(), V2.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
*/


  cout << "DELAUNAY FLIP(exact)  " << flush;
  T = used_time();
  TRIANGULATE_POINTS(L1,D2);
  t1 = used_time(T);
  DELAUNAY_FLIPPING(D2,d_list);
  t2 = used_time(T);
  DELAUNAY_TO_VORONOI(D2,V2);
  t3 = used_time(T);
  cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
          V2.number_of_nodes(), V2.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
 return 0;
}
