Problem 2140 Forever 0.5
Accept: 36 Submit: 113 Special Judge
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem 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
Sample Output
Hint
This problem is special judge.
题意 ：给你一个数n，让你找出n个点，满足一下关系：
- 任意两点的距离不大于1.0
- 所有点到原点的距离不大于1.0
- 恰好有N对点的距离为1.0
- 由这些点构成的n边形的面积不小于0.5
- 由这些点构成的n边形的面积不大于0.75
如果有就输出yes加上这n个点，如果没有就输出no
思路 ： 这个题一开始看样例觉得好复杂，其实画个图推一下倒是可以看出来，要满足上边的条件至少要是4个点，3个点的话是一个等边三角形，面积不符合。因为条件中老是提到1，其实就是一个半径为1的圆以原点为圆心。然后以原点和x轴画一个边长为1的等边三角形，这样的话就有三个点了，其实前四个点都是可以确定的，然后剩下的点从圆上找就可以了，主要是别离那三个点的距离大于1即可，因为圆上的点到圆心的距离都为1，其实就是将圆离散化。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std ;
double x[],y[] ;
const double temp = 0.005 ;
void chart()
{
x[] = ,y[] = ;
x[] = ,y[] = ;
x[] = 0.5,y[] = sqrt(1.0-0.25) ;
x[] = 0.5 ,y[] = y[]- ;
for(int i = ; i < ; i++)
{
y[i] = i*temp ;
x[i] = sqrt(-y[i]*y[i]) ;
}
}
int main()
{
int T,n ;
chart() ;
scanf("%d",&T) ;
while(T--)
{
scanf("%d",&n) ;
if(n < )
printf("No\n") ;
else
{
printf("Yes\n") ;
for(int i = ; i < n ; i++)
printf("%.6lf %.6lf\n",y[i],x[i]) ;
}
}
return ;
}