此文章可以使用目录功能哟↑(点击上方[+])
FZU Problem 2140 Forever 0.5
Accept: 0 Submit: 0 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
2
3
5
Sample Output
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.
Problem Idea
解题思路:
【题意】
给你一个整数n,你的任务是判断平面上是否存在n个点满足下列条件:
1.任意两点间的距离不超过1.0
2.任意一点与原点(0,0)的距离不超过1.0
3.恰好存在n对点,每对中的两点间距离恰好为1.0
4.n个点构成的凸包面积不小于0.5
5.n个点构成的凸包面积不大于0.75
【类型】
计算几何,构造(考查思维)
【分析】
刚开始看这题的时候感觉有些难度,但是其实只要稍微分析一下,答案便会浮出水面
首先,我们可以根据样例判断出n=2和n=3时,为什么是不存在这样的n个点的
很简单
当n=2时,无论怎么构造,都不满足条件3,因为两个点最多只能组成一对点,而条件3要求恰好有n对,显然无法办到
当n=3时,最多只能组成3对,恰好达到条件3的数量限定,这样子的话,那n个点构成的凸包只有一种情况,如下:
该情况下,凸包面积为(√3)/4≈0.433<0.5
故不满足条件4
这时,我们又可以从样例中看到n=5时,是存在这n个点的
且除第一个点外,剩下的点似乎又关于y轴对称
可见,此题必定有什么入手点
考虑到恰好存在n对点,每对点的距离恰好为1.0这个条件
我们应该优先考虑如何构造能够保证恰好只有n对点距离为1.0
因为当n>3时,n个点能组成的点对已经超过n对
本人最先考虑到的构造方法是这样的
但是这样貌似只有n-1对距离为1.0的点对
再想想,对了,怎么忘了n=3时的那种情况呢,只要保证上图中P2和Pn的距离是1.0不就恰好有n对距离为1.0的点对了?
嗯，不错，再想想这种情况会不会超过凸包面积的上界
我们可以知道的是，P2与Pn之间的点越多，这个凸包越接近扇形
那这个扇形必定是面积最大的时候，由于扇形角度是60°，故可以求得扇形面积是1/6圆面积，为π/6≈0.524<0.75，上界显然可以
那我只要保证下界满足就可以了，那我们从n=4开始考虑，理想的构造方法应该是这样的
此时凸包面积恰好为1.0*1.0/2=0.5，符合条件
那当n>4时如何摆放其他点呢?要不都和P4重合吧，于是此题得到完美解决
【时间复杂度&&优化】
O(1)
题目链接→FZU Problem 2140 Forever 0.5
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
int main()
{int t,n,i;scanf("%d",&t);while(t--){scanf("%d",&n);if(n<4){puts("No");continue;}puts("Yes");printf("%.6f %.6f\n",0.0,0.0);printf("%.6f %.6f\n",0.5,0.5*sqrt(3.0));printf("%.6f %.6f\n",-0.5,0.5*sqrt(3.0));for(i=3;i<n;i++)printf("%.6f %.6f\n",0.0,1.0);}return 0;
}