2014
11-05

# Enumerate the Triangles

Little E is doing geometry works. After drawing a lot of points on a plane, he want to enumerate all the triangles which the vertexes are three of the points to find out the one with minimum perimeter. Your task is to implement his work.

The input contains several test cases. The first line of input contains only one integer denoting the number of test cases.
The first line of each test cases contains a single integer N, denoting the number of points. (3 <= N <= 1000)
Next N lines, each line contains two integer X and Y, denoting the coordinates of a point. (0 <= X, Y <= 1000)

The input contains several test cases. The first line of input contains only one integer denoting the number of test cases.
The first line of each test cases contains a single integer N, denoting the number of points. (3 <= N <= 1000)
Next N lines, each line contains two integer X and Y, denoting the coordinates of a point. (0 <= X, Y <= 1000)

2
3
0 0
1 1
2 2
4
0 0
0 2
2 1
1 1

Case 1: No Solution
Case 2: 4.650

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef double DB;
const int N = 1111;
const DB inf = 1e20;
const DB eps = 1e-8;
inline int sgn(DB x) { return fabs(x)<eps ? 0 : x>eps ? 1 : -1; }
struct point {
int x,y;
void input(void) { scanf("%d%d",&x,&y); }
bool operator<(const point &p)const { return x<p.x; }
DB dist(const point &p)const { return hypot((DB)x-p.x,(DB)y-p.y); }
}p[N];
inline bool online(int i,int j,int k) {
return (p[k].x-p[j].x)*(p[j].y-p[i].y)==(p[k].y-p[j].y)*(p[j].x-p[i].x);
}
int main(void) {
int n,t;
DB res,a;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++) {
scanf("%d",&n);
for(int i=0;i<n;i++) p[i].input();
sort(p,p+n);
res=inf;
for(int i=0;i<n-2;i++) for(int j=i+1;j<n-1;j++) {
if(sgn(2.0*(p[j].x-p[i].x)-res)>=0) break;
a = p[i].dist(p[j]);
if(sgn(2*a-res)>=0) continue;
for(int k=j+1;k<n;k++) {
if(sgn(2.0*(p[k].x-p[i].x)-res)>=0) break;
if(online(i,j,k)) continue;
res=min(res,a+p[i].dist(p[k])+p[j].dist(p[k]));
}
}
printf("Case %d: ",cas);
if(res==inf) puts("No Solution");
else printf("%.3f\n",res);
}
return 0;
}

1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

3. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;