【POJ 2187】 Beauty Contest (凸包-Graham扫描算法)
找平面最远点对 数据很大 用暴力会T..我感觉……
扫描出个凸包 然后枚举凸包上的点即可 没坑 int也可过 注意重边跟共线就行 代码下附赠几组数据
代码如下:
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>#include <stack>#include <algorithm>#define ll long longusing namespace std;typedef struct Line Line;typedef struct Point Point;ll mx,my;struct Point{ll x,y;ll operator – (const Point a)const{return (x-a.x)*(x-a.x)+(y-a.y)*(y-a.y);}bool operator < (const Point a)const{if(x == mx && y == my) return false;if(a.x == mx && a.y == my) return true;if((x-mx)*(a.y-my) – (y-my)*(a.x-mx) == 0) return (x-mx)*(x-mx)+(y-my)*(y-my) < (a.x-mx)*(a.x-mx)+(a.y-my)*(a.y-my);return (x-mx)*(a.y-my) – (y-my)*(a.x-mx) > 0;}};struct Line{ll x,y;bool operator > (const Line a)const//顺时针{return x*a.y – y*a.x > 0;}};Point pt[50000];stack <Point> s;vector <Point> tmp;void Read(int &n)//输入并进行极角排序{scanf("%d",&n);int mm = 0;for(int i = 0; i < n; ++i){scanf("%lld %lld",&pt[i].x,&pt[i].y);if(pt[i].x < pt[mm].x || (pt[i].x == pt[mm].x && pt[i].y < pt[mm].y))mm = i;}mx = pt[mm].x;my = pt[mm].y;sort(pt,pt+n);}void SetTb(int n)//建凸包{Point p1,p2;Line l1,l2;s.push(Point{mx,my});s.push(pt[0]);for(int i = 1; i < n; ++i){if(pt[i].x == mx && pt[i].y == my) break;p2 = s.top();s.pop();while(!s.empty()){p1 = s.top();s.pop();l1.x = p2.x – p1.x;l1.y = p2.y – p1.y;l2.x = pt[i].x – p1.x;l2.y = pt[i].y – p1.y;if(l1 > l2){s.push(p1);break;}p2 = p1;}s.push(p2);s.push(pt[i]);}}ll MaxLength()//从栈中不断出栈找最远点距{int i;ll Maxlen = 0;while(!s.empty()){Point tp;tp = s.top();s.pop();for(i = 0; i < tmp.size(); ++i){Maxlen = max(Maxlen,tp-tmp[i]);}tmp.push_back(tp);}return Maxlen;}int main(){int n;Read(n);SetTb(n);printf("%lld\n",MaxLength());return 0;}/*Input:9200 400300 400300 300400 300400 400500 400500 200350 200200 20040 00 10 10 020 00 1Output:13000011*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
，这种精神使人能在旅行中和大自然更加接近，
