http://acm.timus.ru/problem.aspx?num=1207?

題意：給你n個點，讓你在n個點當(dāng)中選兩個點，使得兩邊點的數(shù)量相等；

題解：想找出最靠左邊的最下邊的點，以這個點求極角，然后排序 ，它的一半就是我們所要求的點

code：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> 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;;} }

總結(jié)

以上是生活随笔為你收集整理的Ural 1207. Median on the Plane（计算几何）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。