「凸四边形」Forever 0.5 FZU - 2140 （判断凸四边形）

凸四边形

Given an integer N, your task is to judge whether there exist N points in the plane such that satisfy the following conditions:

1. The distance between any two points is no greater than 1.0.

2. The distance between any point and the origin (0,0) is no greater than 1.0.

3. There are exactly N pairs of the points that their distance is exactly 1.0.

4. The area of the convex hull constituted by these N points is no less than 0.5.

5. The area of the convex hull constituted by these N points is no greater than 0.75.

Input

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each contains an integer N described above.

1 <= T <= 100, 1 <= N <= 100

Output

For each case, output “Yes” if this kind of set of points exists, then output N lines described these N points with its coordinate. Make true that each coordinate of your output should be a real number with AT MOST 6 digits after decimal point.

Your answer will be accepted if your absolute ERROR for each number is no more than 10-4.

Otherwise just output “No”.

See the sample input and output for more details.

Sample Input

Sample Output

No
No
Yes
0.000000 0.525731
-0.500000 0.162460
-0.309017 -0.425325
0.309017 -0.425325
0.500000 0.162460

Hint

This problem is special judge.

1）角度法：

判断每个顶点所对应的内角是否小于180度，如果小于180度，则是凸的，如果大于180度，则是凹多边形。

2）凸包法：

这种方法首先计算这个多边形的凸包，关于凸包的定义在此不再赘述，首先可以肯定的是凸包肯定是一个凸多边形。如果计算出来的凸多边形和原始多边形的点数一样多，那就说明此多边形时凸多边形，否则就是凹多边形。

3）顶点凹凸性法

利用以当前顶点为中心的矢量叉乘或者计算三角形的有符号面积判断多边形的方向以及当前顶点的凹凸性。

假设当前连续的三个顶点分别是P1，P2，P3。计算向量P1P2,P2P3的叉乘，也可以计算三角形P1P2P3的面积，得到的结果如果大于0，则表示P3点在线段P1和P2的左侧，多边形的顶点是逆时针序列。然后依次计算下一个前后所组成向量的叉乘，如果在计算时，出现负值，则此多边形时凹多边形，如果所有顶点计算完毕，其结果都是大于0，则多边形时凸多边形。

4）辛普森面积法

利用待判别的顶点以及前后两个顶点所组成的三角形，利用辛普森公式计算其面积，如果此三角形面积与整个多边形面积符号相同，那么这个顶点是凸的；如果此三角形面积与整个多边形面积符号不同，那么这个顶点是凹的，即整个多边形也是凹多边形。

#include<iOStream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 1e-8
using namespace std;
struct node{
	int x,y;
}arr[35];
double area(node a,node b,node c){//求三角形面积，点乘积 
	node ab,ac;
	ab.x=b.x-a.x;
	ab.y=b.y-a.y;
	ac.x=c.x-a.x;
	ac.y=c.y-a.y;
	return fabs(ab.x*ac.y-ab.y*ac.x)*1.0/2.0;
}
int judge(node a,node b,node c,node d){//判断凸包 
	if(fabs(area(b,c,d)-area(a,b,c)-area(a,c,d)-area(a,b,d))<eps) return 1;
	return 0;
}
int check(node a,node b,node c,node d){//判断凸四边形 
	if(judge(a,b,c,d)) return 0;
	if(judge(b,a,c,d)) return 0;
	if(judge(c,a,b,d)) return 0;
	if(judge(d,a,b,c)) return 0;
	return 1;
}
int main(){
	int T,Cas=0;
	scanf("%d",&T);
	while(T--){
		memset(arr,0,sizeof(arr));
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		   scanf("%d%d",&arr[i].x,&arr[i].y);
		int ans=0;
		for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
		for(int a=j+1;a<n;a++)
		for(int b=a+1;b<n;b++)
		  if(check(arr[i],arr[j],arr[a],arr[b])) ans++;
		printf("Case %d: %d\n",++Cas,ans);
	}
	return 0;
}

Forever 0.5 FZU - 2140 （判断凸四边形）

凸四边形

相关阅读

栏目导航

推荐阅读

热门阅读