放盘子
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Case #1: Give me a kiss! Case #2: I want to kiss you!
Hint
在第一组样例中，小度熊先在多边形中间放一个盘子，接下来无论来访者怎么放，小度熊都根据多边形中心与来访者的盘子对称着放就能获胜。
Problem's Link: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1004
analyse:
SB题。
策略是这样的：因为是百度熊先放，如果可以放第一个，百度熊就将这个盘子放在正多边形的中央(盘子圆心和正多边形的中心重合)，剩下的就是别人怎么放，百度熊跟着放在对称的位置就行。因为：边数为偶数的正多边形一定是关于几何中心对称。
问题就简化成了：如果能放下第一个盘子，百度熊就一定能赢。
只需要求出正多边形对边的距离和2*r相比较即可。
Time complexity: O(n)
Source code:
Java代码：
import java.util.Scanner; public class Main { static Scanner in=new Scanner(System.in); double calcLen(int n,double a) { if(n==4) return a/2.0; double PI=3.1415926; return a/2.0/(Math.tan(PI*360.0/(double)n/2.0/180)); } public static void main(String[] args) { int t=in.nextInt(); for(int Cas=1;Cas<=t;++Cas) { int n; double a,r; n=in.nextInt(); a=in.nextDouble(); r=in.nextDouble(); System.out.println("Case #"+Cas+":"); double len=new Main().calcLen(n,a); if(len-r>=0.0) System.out.println("Give me a kiss!"); else System.out.println("I want to kiss you!"); } } }
C++代码：
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-24-19.09 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; int i, t, n; double a, r, x, y; int main() { scanf( "%d", &t ); for ( i = 1; i <= t; i++ ) { scanf( "%d%lf%lf", &n, &a, &r ); printf( "Case #%d:\n", i ); x = ( 90 * n - 180 ) / n; y = a / 2 * tan( x / 180 * 3.1415927 ); if ( y < r ) {printf( "I want to kiss you!\n" ); continue;} printf( "Give me a kiss!\n" ); continue; } return 0; }
