倾斜的线

(slope.cpp)

【问题描述】

给定两个正整数P和Q。在二维平面上有n个整点。现在请你找到一对点使得经过它们的直线的斜率在数值上最接近P/Q（即这条直线的斜率与P/Q的差最小），请输出经过它们直线的斜率p/q。如果有两组点的斜率的接近程度相同，请输出较小的斜率。保证答案的p/q> 0，即输出的p和q都是正整数。

【输入格式】

输入文件名为slope.in。

第一行三个正整数n P Q。

接下来n行每行两个正整数x y表示一个点的坐标。保证不存在x坐标相同或者y坐标相同的点（即斜率不会为无穷大与0）。

【输出格式】

输出文件名为slope.out。

输出仅一行，格式为p/q，表示最接近的斜率，其中p和q都是正整数。

【样例输入与输出】

example_slope1.in	example_slope1.out
6 15698 17433 112412868 636515040 122123982 526131695 58758943 343718480 447544052 640491230 162809501 315494932 870543506 895723090	193409386/235911335

       更多样例请见example/slope/目录。

【数据范围】

对于1~10号测试点（50%）：n<=1000。

对于所有测试点（100%）：n<=400000。

 

 

 

 

把所有点按照P/Q斜率投射到y轴上排序，可以证明相邻的点对应的线段一定有一条是最优解，因为不相邻的点与给定的斜率夹角比相邻的大

code：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define N 1000006  6 using namespace std; 7 struct node{ 8     long double x,y,w; 9 }e[N];10 bool cmp(const node&a,const node&b){11     return a.w
         
          >n>>P>>Q;25     for(int i=1;i<=n;i++){26         cin>>e[i].x>>e[i].y;27         e[i].w=e[i].y-e[i].x*P/Q;28     }29     sort(e+1,e+n+1,cmp);30     long double delta=9999999.0;31     int now1,now2;32     for(int i=1;i
         
        
       
      
     

over