首页 > ACM题库 > HDU-杭电 > HDU 3532-Max Angle[解题报告]HOJ
2014
11-05

HDU 3532-Max Angle[解题报告]HOJ

Max Angle

问题描述 :

Given many points in a plane, two players are playing an interesting game.

Player1 selects one point A as the vertex of an angle. Then player2 selects other two points B and C. A, B and C are different with each other. Now they get an angle B-A-C.

Player1 wants to make the angle as large as possible, while player2 wants to make the angle as small as possible.

Now you are supposed to find the max angle player1 can get, assuming play2 is c lever enough.

输入:

There are many test cases. In each test case, the first line is an integer n (3 <= n <= 1001), which is the number of points on the plane. Then there are n lines. Each contains two floating number x, y, witch is the coordinate of one point. n <= 0 denotes the end of input.

输出:

There are many test cases. In each test case, the first line is an integer n (3 <= n <= 1001), which is the number of points on the plane. Then there are n lines. Each contains two floating number x, y, witch is the coordinate of one point. n <= 0 denotes the end of input.

样例输入:

3
0 0
2 0
0 5
-1

样例输出:

90.0000

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define pi 3.141592653589793
using namespace std;

struct node
{
 double x, y;
};
node list[1001];
double k[1001];
int n;

int main()
{
 int i, j, index;
 double ans, xx, yy, bad, min;

 while(scanf("%d", &n) && n>0)
 {
 for(i=0; i<n; i++) scanf("%lf%lf", &list[i].x, &list[i].y);
 
 ans = 0;
 for(i=0; i<n; i++)
 {
 index = 0; min = 361;
 for(j=0; j<n; j++) 
 if (i != j)
 {
 xx = list[j].x-list[i].x;
 yy = list[j].y-list[i].y;
 k[index++] = atan2(yy, xx)*180/pi;
 if (k[index-1] < 0) k[index-1] += 360;
 }
 
 sort(k, k+index);
 
 for(j=1; j<index; j++)
 {
 bad = k[j]-k[j-1];
 if (bad < min) min = bad;
 } 
 bad = 360-k[index-1]+k[0];
 if (bad < min) min = bad;

 if (min > ans) ans = min; 
 }
 printf("%.4lf\n", ans);
 }
 return 0; 
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish