POJ(2187)用凸包求最远点对
时间:2014-01-14 19:24:56
收藏:0
阅读:754
Beauty Contest
http://poj.org/problem?id=2187
题目描述:输入n对整数点,求最距离远的点对,输出他们距离的平方和
算法:拿到这个题,最朴素的想法就是用2层循环遍历所有的点对,但这样可能会超时。由于距离最远的点对必定在点集的凸包的顶点上,所以只用遍历凸包上的点对就行。这样就把可能存在的大量的点给排除。哈哈~~~还是凸包。
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <cmath> using namespace std; struct Node { int x,y; Node operator-(Node &node) { Node new_node; new_node.x=x-node.x; new_node.y=y-node.y; return new_node; } }; vector<Node> p,s; //p存放所有顶点,s存放凸包顶点,s模拟栈 const double eps=10e-6; int squared_distance(Node &a,Node &b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } double cross(Node vec1,Node vec2) { return (double)(vec1.x*vec2.y-vec1.y*vec2.x); } bool cmp(Node &a,Node &b) { Node vec1=a-p[0]; Node vec2=b-p[0]; double temp=cross(vec1,vec2); if(temp>eps) return true; else if(temp<eps) return false; else { if(squared_distance(a,p[0])<squared_distance(b,p[0])) return true; else return false; } } void swap(Node &a,Node &b) { Node temp; temp=a; a=b; b=temp; } int lowleft(vector<Node> &p) { int len=p.size(); int min_x=p[0].x,min_y=p[0].y; int k=0; for(int i=0;i<len;i++) { if(p[i].y<min_y) { min_x=p[i].x; min_y=p[i].y; k=i; } else if(p[i].y==min_y&&p[i].x<min_x) { min_x=p[i].x; k=i; } } return k; } void graham(vector<Node> &p) { int k=lowleft(p); swap(p[0],p[k]); sort(p.begin()+1,p.end(),cmp); p.push_back(p[0]); s.push_back(p[0]); s.push_back(p[1]); int top=1; int len=p.size(); for(int i=2;i<len;i++) { while(top>=1&&cross(s[top]-s[top-1],p[i]-s[top])<0) { s.pop_back(); top--; } s.push_back(p[i]); top++; } } int main() { int n; while(cin>>n) { Node temp; p.clear(); s.clear(); for(int i=0;i<n;i++) { cin>>temp.x>>temp.y; p.push_back(temp); } graham(p); int max=0; int len=s.size()-1;//p的最后一个元素的值是p[0]遍历 for(int i=0;i<len-1;i++) { for(int j=i+1;j<len;j++) { int d=squared_distance(s[i],s[j]); if(d>max) max=d; } } cout<<max<<endl; } return 0; }
原文:http://www.cnblogs.com/chiry/p/3512213.html
评论(0)