Enumerate the Triangles&&http://cdn.ac.nbutoj.com/Contest/view/id/14/problem/E.xhtml

问题描述

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)

输出

For each test cases, output the minimum perimeter, if no triangles exist, output "No Solution".

样例输入

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

题意：给你一些点，让你求这些点组成的最小三角形的面积，如果不存在则输出No sluation，

思路：常规方法，暴力枚举，但是一定要注意剪枝，这里排序的目的就是为了剪枝，，，囧，，

AC代码：

#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 1001
using namespace std;
typedef struct str
{
	int x;
	int  y;
}Node;
Node s[N];
int Scan()
{
	int num = 0 , ch ;
	while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) )
	{
		if( ch == EOF )  return 1 << 30 ;
	}
	num = ch - '0' ;
	while( ( ch = getchar() ) >=  '0' && ch <=  '9' )
		num = num * 10 + ( ch - '0' ) ;
	return num;
}
 bool  cmp(Node a,Node b)
{return ((a.x<b.x)||(a.x==b.x&&a.y<b.y));}
 double distan(Node a,Node b)
{return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
 bool  line(Node a,Node b,Node c)判断三点是不是共线
{
	a.x-=c.x;
	a.y-=c.y;
	b.x-=c.x;
	b.y-=c.y;
	return a.x*b.y==a.y*b.x;
}
int main()
{
	int T=Scan();
	for(int xx=1;xx<=T;++xx)
	{   
		int n=Scan();
		for(int i=0;i!=n;++i)
		 s[i].x=Scan(),s[i].y=Scan();
		   sort(s,s+n,cmp);
		   double ans=1e10;
		   for(int i=0;i!=n;++i)
		   {
			   for(int j=i+1;j!=n;++j)
			   {
				   if(2*abs(s[j].x-s[i].x)>ans) break;
				   if(2*distan(s[j],s[i])>ans) continue;
				   for(int k=j+1;k!=n;++k)
				   {  
					   if(line(s[k],s[j],s[i])) continue;
					   if(2*abs(s[k].x-s[i].x)>ans) break;
					   double res=distan(s[i],s[j])+distan(s[i],s[k])+distan(s[j],s[k]);
					   if(res<ans) ans=res;
					}
			   }
		   }
		   if(ans<1e10) printf("Case %d: %.3lf\n",xx,ans);
		   else     printf("Case %d: No Solution\n",xx);
	}return 0;
}