#1687 : 寻找切线

时间限制:

10000ms

单点时限:

1000ms

内存限制:

256MB

描述

给定平面上N个点P₁=(X₁, Y₁), P₂=(X₂, Y₂), ... P_N=(X_N, Y_N)。  

请你从中找到两个不同的点P_i和P_j满足：其他所有点都在P_i和P_j连线的同一侧(可以在连线上)。

如果有多组答案满足条件，你可以输出任意一组。

输入

第一行包含一个整数N。  

以下N行每行包含两个整数X_i和Y_i。  

对于50%的数据，1 ≤ N ≤ 1000  

对于100%的数据，1 ≤ N ≤ 100000 0 ≤ X_i, Y_i ≤ 1000000

输出

输出由一个空格隔开的两个整数i和j，注意1 ≤ i, j ≤ N且i ≠ j。

样例输入

6  0 10  7 0  8 8  10 18  15 13  20 4

样例输出

5 6 分析：先按一定顺序排序，再用向量叉积更新某一侧的点。

#include
           
            #include
            
             #include
             
              #include
              
                using namespace std;struct Node{    double x,y;    int num;}a[220000];int cmp(Node A,Node B){    if(A.x>B.x) return 1;    else if(A.x==B.x&&A.y
               
                0)         {            index=i;            x1=x2;y1=y2;        }    }    printf("%d %d\n",a[0].num,a[index].num);    return 0;}