2015
04-13

# 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

Problem Description
The Kingdom of Silence is a beautiful country. There are N cities in the kingdom. There are several highways so that people can go from a city to another one. But there are so many cars in the kingdom that there are too many traffic congestions in the kingdom.

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.

Input
The first line contains a single integer T, the number of test cases. And then followed T cases.

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.

Output
The output should contain T lines. For each test case you should just output an real number with exactly three digits after a decimal point which is the least money that the king have to pay.

Sample Input
1 4 0 0 0 1 1 0 5 5

Sample Output
3.414
Hint
In the sample we can choose the first three cities to build the transmitter.

Source

#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;
}

1. E一定会死，球碰到斜面后会落到右边那个杠杆上，翘起那个残缺的球，残缺的球会滚动，缺口正好越过D的头，然后……E就被砸死了

2. E一定会死，球碰到斜面后会落到右边那个杠杆上，翘起那个残缺的球，残缺的球会滚动，缺口正好越过D的头，然后……E就被砸死了

3. E一定会死，球碰到斜面后会落到右边那个杠杆上，翘起那个残缺的球，残缺的球会滚动，缺口正好越过D的头，然后……E就被砸死了

4. E一定会死，球碰到斜面后会落到右边那个杠杆上，翘起那个残缺的球，残缺的球会滚动，缺口正好越过D的头，然后……E就被砸死了

5. E一定会死，球碰到斜面后会落到右边那个杠杆上，翘起那个残缺的球，残缺的球会滚动，缺口正好越过D的头，然后……E就被砸死了

6. E一定会死，球碰到斜面后会落到右边那个杠杆上，翘起那个残缺的球，残缺的球会滚动，缺口正好越过D的头，然后……E就被砸死了

7. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}