题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4946
题目的意思是,给一些点,(代表学生),和这些点的速度,这些点要占领其他点(平面上所有的点,都是可以占领的),问这些点可以占领点是否是无限的。一个点被占领后,不能被其他的点占领。某一个点属于某个学生(也就是点),是走到该点所用时间小于其他所有点的时间。一开始,理解不了。以为,这些点都是动态的吧。其实,不然,其实判断某个点属于某个学生,只需要判断走到该点时间即可。。
思路:
官方题解的思路很好。
Code:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int N = 505; const double eps = 1e-8; struct POINT { double x, y; double v; int no; }p[N], st[N], sp[N]; int n, m, top, ans[N]; double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); } double Distance(POINT a, POINT b){ return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } bool cmp(POINT a, POINT b){ if(a.y < b.y || (a.y == b.y && a.x < b.x)) return true; return false; } bool cmp1(POINT a, POINT b){ double k = cross(p[0], a, b); if(k > eps) return true; else if(fabs(k) < eps && (Distance(p[0], a) - Distance(p[0], b)) < eps) return true; return false; } bool Judge(POINT a, POINT b, POINT c){ double k = cross(a, b, c); if(k > eps) return true; else return false; } void Graham_scan(){ if(n == 1) { if(ans[p[0].no] == -1) ans[p[0].no] = 1; return ; } sort(p, p + n, cmp); sort(p + 1, p + n, cmp1); top = 0; st[top ++] = p[0]; st[top ++] = p[1]; for(int i = 2; i < n; i ++){ while(top >= 2 && Judge(st[top - 1], st[top - 2], p[i])) top --; st[top ++] = p[i]; } int ltop = top; for(int i = n - 2; i >= 0; i --){ while(top != ltop && Judge(st[top - 1], st[top - 2], p[i])) top --; st[top ++] = p[i]; } top --; }//fisrt del the same point, stay one of the maxv. int main(){ // freopen("input.txt", "r", stdin); int k = 0, s; while(scanf("%d", &n) && n){ s = n; memset(ans, -1, sizeof(ans)); double maxv = -1; for(int i = 0; i < n; i ++){ scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].v); p[i].no = i; maxv = max(maxv, p[i].v); } printf("Case #%d: ", ++ k); if(maxv == 0){ for(int i = 0; i < n; i ++){ printf("0"); } printf("\n"); continue; } m = 0; for(int i = 0; i < n; i ++){// v == maxv if(p[i].v != maxv) ans[p[i].no] = 0; else sp[m ++] = p[i]; } sort(sp, sp + m, cmp);// del the same point. n = 0; p[n ++] = sp[0]; for(int i = 1; i < m; i ++){ if(!(sp[i].x == sp[i - 1].x && sp[i].y == sp[i - 1].y)) p[n ++] = sp[i]; else { ans[sp[i].no] = 0; ans[sp[i - 1].no] = 0; } } Graham_scan(); for(int i = 0; i < top; i ++){ if(ans[st[i].no] == -1) ans[st[i].no] = 1; } for(int i = 0; i < s; i ++){ if(ans[i] == -1) ans[i] = 0; } for(int i = 0; i < s; i ++){ printf("%d", ans[i]); } puts(""); } return 0; }