FZU 2140 Forever 0.5 (几何构造)

时间:2021-04-15 06:44:12
Forever 0.5

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

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

3
2
3
5

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.

题意:找n个点满足上述五个条件。

题解:n=1和n=2的时候不能构成多边形输出No,n=3的时候最大是边长为1的等边三角形,面积为4分之根号3小于0.5不符合条件输出No。当n=4的时候,在等边三角形的一个顶点的高的方向加一个点,距离该顶点的距离为1即可满足五个条件,如图所示。

FZU 2140 Forever 0.5 (几何构造)

AC=AB=BC=BD=1。多边形外侧是一个以(0,0)为圆心半径为1的圆。

当n>=5时,在BC弧上加点即可,Smax=S扇形ABC+S三角形ACD=pi/6+1*(1-sqrt(3)/2)/2=0.59058。符合条件。

角bac是60度也就是pi/3,新加入的点的弧度f为pi/3-0.01*(n-4)即可,n最大100,最多加入96个点不会溢出。

新加入点的横坐标就是cos(f),纵坐标就是sin(f)。用y=sqrt(1-x*x)算也行。

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define pi 3.1415926535897931
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
if(n<=)
{
printf("No\n");
}
else
{
printf("Yes\n"); //开始的时候忘了输出Yes错了三遍
double a=sqrt()/2.0;
printf("0 0\n");
printf("1 0\n");
printf("0.5 %.6lf\n",a);
printf("0.5 %.6lf\n",a-);
double b=pi/3.0;
for(int i=;i<n-;i++)
{
b=b-0.01;
printf("%.6lf %.6lf\n",cos(b),sin(b));
}
}
}
return ;
}