本文共 3011 字，大约阅读时间需要 10 分钟。
题意：给你n个点，让你在n个点当中选两个点，使得两边点的数量相等；
题解：想找出最靠左边的最下边的点，以这个点求极角，然后排序 ，它的一半就是我们所要求的点
code：
#include#include #include #include #include using namespace std;#define eps 1e-8//点struct POINT{ double x, y; int pnd; POINT(){ } POINT(double a, double b){ x = a; y = b; }}p[10005];//线段struct Seg{ POINT a, b; Seg() { } Seg(POINT x, POINT y){ a = x; b = y; }};//叉乘double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}//判断点在线段上//bool On_Seg(POINT a, Seg s)//{// double maxx = max(s.a.x, s.b.x), minx = min(s.a.x, s.b.x);// double maxy = max(s.a.y, s.b.y), miny = min(s.a.y, s.b.y);// if(a.x >= minx && a.x <= maxx && a.y >= miny && a.y <= maxy) return true;// return false;//}判断线段相交//bool Seg_cross(Seg s1, Seg s2)//{// double cs1 = cross(s1.a, s2.a, s2.b);// double cs2 = cross(s1.b, s2.a, s2.b);// double cs3 = cross(s2.a, s1.a, s1.b);// double cs4 = cross(s2.b, s1.a, s1.b);// // 互相跨立// if(cs1 * cs2 < 0 && cs3 * cs4 < 0) return true;// if(cs1 == 0 && On_Seg(s1.a, s2)) return true;// if(cs2 == 0 && On_Seg(s1.b, s2)) return true;// if(cs3 == 0 && On_Seg(s2.a, s1)) return true;// if(cs4 == 0 && On_Seg(s2.b, s1)) return true;// return false;//}求两条线段的交点，但是，必须保证线段相交且不共线共线的话需要特判//POINT Inter(Seg s1, Seg s2)//{// double k = fabs(cross(s1.a, s2.a, s2.b)) / fabs(cross(s1.b, s2.a, s2.b));// return POINT((s1.a.x + s1.b.x * k) / (1 + k), (s1.a.y + s1.b.y * k) / (1 + k));//}多边形面积，需要有顺序，顺(逆)时针。//double area()//{// double ans = 0;// for(int i = 1; i < top; i ++){// ans += cross(p[0], p[i], p[i + 1]);// }// return ans;//}找凸包基点排序//bool cmp0(POINT a, POINT b)//{// if(a.y < b.y) return true;// else if(a.y == b.y && a.x < b.x) return true;// return false;//}//极角排序double dis(POINT a , POINT b){ return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );}bool cmp1(POINT a, POINT b){ if(cross(p[0], a, b) > eps) return true; else if(fabs(cross(p[0], a, b)) < eps && dis(p[0], a) - dis(p[0], b) > eps) return true; return false;}Graham_scan 求凸包.所求为纯净凸包...//void Graham_scan()//{// sort(p, p + n, cmp0);// sort(p + 1, p + n, cmp1);// top = 0;// p[n] = p[0];// st[top ++] = p[0]; st[top ++] = p[1];// for(int i = 2; i <= n; i ++){// while(top > 2 && (cross(st[top - 1], st[top - 2], p[i]) > eps || fabs(cross(st[top - 1], st[top - 2], p[i])) < eps)) top --;// st[top ++] = p[i];// }// top --;//}int main(){ int n; while(cin >> n){ for(int i = 0;i < n;i++){ cin >> p[i].x >> p[i].y; p[i].pnd = i + 1; } int tmp = 0; for(int i = 1;i < n;i++) { if(p[i].x < p[tmp].x || (p[i].x == p[tmp].x && p[i].y < p[tmp].y)) tmp = i; } swap(p[0],p[tmp]); sort(p+1,p+n,cmp1); cout << p[0].pnd << " " << p[n/2].pnd << endl;; }}
转载地址：http://acsgi.baihongyu.com/