The Triangle ransmitter
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 219 Accepted Submission(s): 89
In order to solve the problem, Dr. Lin made a new invention named Triangle Transmitter. This transmitter is designed to travel among three cities and no matter how long the distance is, we can reach our destination in the three cities in 1 second.
Although the Triangle Transmitter is so excellent, it is so expensive that the king can only build one transmitter to test it. Because it is only for testing, we should make it as cheap as possible. If we build a Triangle Transmitter in three cities, the money we will pay is equal to the sum of the distance between every two cities in the three cities.
Now it is your job to choose three cities to build a Triangle Transmitter so that the king will spend least money. What's more, the king will give you the number of the cities N and the position of each city. The position of each city is described by two integers xi and yi, the distance between two cities is sqrt((xi - xj)^2 + (yi - yj)^2). And no two cities have the same position.
In the first line of each test case, there is one integer N (3<=N<=20000) indicates the number of the cities and the cities are numbered from 1 to N.
Then followed N lines, in each line there are two integers xi and yi (0<=xi,yi<=10^9), indicates the position of each city.
1 4 0 0 0 1 1 0 5 5
3.414HintIn the sample we can choose the first three cities to build the transmitter.
这题做的快吐血了……orz,本来就不适合做计算几何的……呃……
好吧,题意很简单,就是给n个点,问这n个点中取三个点,使得两两距离之和最小,问这个和是多少。
其实套一个最近点对的模板就可以了,先x排序,分治,然后如果只剩下6个以内的点就可以直接处理了,如果继续分剩下2个点就变得不太好处理了(至少对我来说-_-|||)。
之后分治完之后跟最近点对一样,在mid点左右ret/2的带状区域内把所有点找出来,对y排序,这时候两点距离小于ret/2的点只可能存在于任意点周围(排序后的顺序)最多7个点中,这样排序后每次找临近7个点就行了。(这部分证明在算法导论的最近点对中有提到)
附代码
#include <stdio.h> #include <algorithm> #include <math.h> using namespace std; #define eps 1e-6 typedef struct { double x,y; }point; point a[20005]; double ret; point tag[20005]; double Dist(point p,point q) { return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)); } bool cmpx(point p,point q) { if (p.x!=q.x) return p.x<q.x; return p.y<q.y; } bool cmpy(point p,point q) { if (p.y!=q.y) return p.y<q.y; return p.x<q.x; } void Merge(int l,int r) { int mid,x,y,i,j,k; double m; if (r-l+1<=6) { for (i=l;i<=r;i++) { for (j=i+1;j<=r;j++) { m=Dist(a[i],a[j]); if (m>ret/2) continue; for (k=j+1;k<=r;k++) { ret=min(ret,m+Dist(a[j],a[k])+Dist(a[i],a[k])); } } } return; } mid=(l+r)/2; Merge(l,mid); Merge(mid+1,r); int up=0; for (i=l;i<=r;i++) { if (fabs(a[mid].x-a[i].x)<ret/2) tag[up++]=a[i]; } sort(tag,tag+up,cmpy); for (i=0;i<up;i++) { for (j=i+1;j<up && j<=i+7;j++) { m=Dist(tag[i],tag[j]); if (m>ret/2) continue; for (k=j+1;k<up && k<=j+7;k++) { ret=min(ret,m+Dist(tag[j],tag[k])+Dist(tag[i],tag[k])); } } } } int main() { int i,j,n,T; scanf("%d",&T); while(T--) { scanf("%d",&n); for (i=0;i<n;i++) { scanf("%lf%lf",&a[i].x,&a[i].y); } sort(a,a+n,cmpx); ret=999999999; Merge(0,n-1); printf("%.3lf\n",ret); } return 0; }