HDU 4946 - Area of Mushroom （计算几何　凸包）

时间：2021-10-17 20:54:29

Area of Mushroom

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1748    Accepted Submission(s): 423



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 
 
 

   3 0 0 3 1 1 2 2 2 1 0 
 
 

 


    

 


  Sample Output 

 

 
 
 
 

   Case #1: 100 
 
 

 


    

 


  Source 

 

 
 2014 Multi-University Training Contest 8 

 


    

 


  Recommend 

 


  hujie   |   We have carefully selected several similar problems for you:   
 4955  
 4954  
 4953  
 4952  
 4951  

 


    

 

 
 


 



 


 


 


 

题意：
 

给定ｎ个人　包含坐标ｘｙ和速度ｖ，如果一个点被一个人占有是指这个人比其他任何人都能先到达这个点。
 

对于这ｎ个人中的第ｉ个人，如果他占有的面积为无穷大，就输出１，否则输出０
 


 


 

第一次写凸包　记录一下　
 

肯定速度最大的才有可能占有面积无穷
 

则所有最大速度的点构成的凸包上的点可以占有无穷面积
 

如果同一个点有两个速度都为最大的点（如果是一个最大，一个不是最大，那么最大的点如果在凸包上，则可以占领无穷的面积），则这两个点的结果都为０
 


 


 

 

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>

using namespace std;

//#define WIN
#ifdef WIN
typedef __int64 LL;
#define iform "%I64d"
#define oform "%I64d\n"
#define oform1 "%I64d"
#else
typedef long long LL;
#define iform "%lld"
#define oform "%lld\n"
#define oform1 "%lld"
#endif

#define S64I(a) scanf(iform, &(a))
#define P64I(a) printf(oform, (a))
#define P64I1(a) printf(oform1, (a))
#define REP(i, n) for(int (i)=0; (i)<n; (i)++)
#define REP1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FOR(i, s, t) for(int (i)=(s); (i)<=(t); (i)++)

const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = (4.0*atan(1.0));

const int maxn = 1000 + 20;

struct Point {
    double x, y, v;
    int id;
    Point(double x=0, double y=0) : x(x), y(y) {}
} A[maxn], B[maxn];
int ans[maxn];

typedef Point Vector;

Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); }

double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }



bool cmp(Point a, Point b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool cmpByV(Point a, Point b) {
    return a.v > b.v;
}

int dcmp(double x) {
    if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}

int ConvexHull(Point * p, int n, Point * ch) {
    sort(p, p+n, cmp);
    int m = 0;
    for(int i=0; i<n; i++) {
        while(m > 1 && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) < 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i=n-2; i>=0; i--) {
        while(m > k  && dcmp(Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) < 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    return m;
}

Point ret[maxn];

int main() {
    int n;
    int kase = 1;

    //freopen("1002.in", "r", stdin);
    //freopen("1002_1.out", "w", stdout);
    while(scanf("%d", &n) != EOF && n) {
        double maxv = 0;
        for(int i=0; i<n; i++) {
            scanf("%lf%lf%lf", &A[i].x, &A[i].y, &A[i].v);
            A[i].id = i;
            maxv = max(maxv, A[i].v);
        }
        if(maxv < eps) {
            printf("Case #%d: ", kase++);
            for(int i=0; i<n; i++) putchar('0');
            putchar('\n');
            continue;
        } 
        sort(A, A+n, cmpByV);
        int m = 0;
        while(m < n && dcmp(A[m].v-maxv) == 0) {
            B[m] = A[m];
            m++;
        }
        sort(B, B+m, cmp);
        int t = 1;
        for(int i=1; i<m; i++) {
            if(dcmp(B[i].x - B[t-1].x) != 0 || dcmp(B[i].y - B[t-1].y) != 0) B[t++] = B[i];
        }
        int rm = ConvexHull(B, t, ret);
        memset(ans, 0, sizeof(ans));
        for(int i=0; i<rm; i++) {
            ans[ret[i].id] = 1;
        }
        for(int i=0; i<m; i++) {
            for(int j=i+1; j<m; j++) {
                if(dcmp(A[i].x - A[j].x) == 0 && dcmp(A[i].y - A[j].y) == 0) {
                    ans[A[i].id] = ans[A[j].id] = 0;
                }
            }
        }
        printf("Case #%d: ", kase++);
        for(int i=0; i<n; i++) printf("%d", ans[i]);
        putchar('\n');
    }

    return 0;
}





 


 


 


标签：
相关文章