首页 > ACM题库 > HDU-杭电 > HDU 3548-Enumerate the Triangles[解题报告]HOJ
2014
11-05

HDU 3548-Enumerate the Triangles[解题报告]HOJ

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;