程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4946 Area of Mushroom(凸包)

HDU 4946 Area of Mushroom(凸包)

編輯：C++入門知識

HDU 4946 Area of Mushroom(凸包)

如果一個人能統治無窮遠處，那麼他的速度一定是最大的。除了那幾種很坑的數據，比如同一個點速度相同的兩個人。永遠都是不可能。所以你要處理出來所有速度最大的點，然後用他們構成一個凸包，你把端點的點求出來了，還得判斷一下在邊上的情況。然後頂點和在邊上的點所構成的就是可以到達無窮遠處的人。

PS：抄了芳姐的模版。。哈哈哈

Area of Mushroom

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 676 Accepted Submission(s): 120

Problem Description Teacher Mai has a kingdom with the infinite area.

He has n students guarding the kingdom.

The i-th student stands at the position (x_i,y_i), and his walking speed is v_i.

If a point can be reached by a student, and the time this student walking to this point is strictly less than other students, this point is in the charge of this student.

For every student, Teacher Mai wants to know if the area in the charge of him is infinite.
Input There are multiple test cases, terminated by a line "0".

For each test case, the first line contains one integer n(1<=n<=500).

In following n lines, each line contains three integers x_i,y_i,v_i(0<=|x_i|,|y_i|,v_i<=10^4).
Output For each case, output "Case #k: s", where k is the case number counting from 1, and s is a string consisting of n character. If the area in the charge of the i-th student isn't infinite, the i-th character is "0", else it's "1".
Sample Input

Sample Output

Case #1: 100

Source 2014 Multi-University Training Contest 8

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-9
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)0;
}
int graham(int n)///返回點的個數
{
    int i,k =0 ,top;
    if(n<2) return 0;
    point tmp ;
    for(i = 0; i < n ; i++)
    {
        if(dcmp(p[i].y-p[k].y)<0||(dcmp(p[i].y-p[k].y)==0&&dcmp(p[i].x-p[k].x)<0))
            k = i;
    }
    swap(p[k],p[0]);
    sort(p+1,p+n,cmp);
    ch[0] = p[0];
    ch[1] = p[1];
    top = 1;
    for(i = 2; i < n ; i++)
    {
        while(top>0&&dcmp(mul(ch[top-1],ch[top],p[i]))<=0) top--;
        top++;
        ch[top] = p[i];
    }
    return top;
}
bool cmpp(point a,point b)
{
    if(a.x==b.x) return a.y>n)
    {
        if(!n) break;
        memset(f, 0, sizeof(f));
        int Max = -INF;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d %d %d",&q[i].x, &q[i].y, &q[i].v);
            q[i].id = i;
            if(!q[i].v) f[i] = -2;
            Max = max(Max, q[i].v);
        }
        for(int i = 1; i <= n; i++)
        {
            if(q[i].v != Max) continue;
            for(int j = i+1; j <= n; j++)
            {
                if(q[j].x == q[i].x && q[j].y == q[i].y && q[j].v == q[i].v)
                {
                    f[q[j].id] = -1;
                    f[q[i].id] = -1;
                }
            }
        }
        int t = 0;
        for(int i = 1; i <= n; i++)
            if(q[i].v == Max && f[q[i].id] != -2) p[t++] = q[i];
        int m = graham(t);
        cout<<"Case #"<