Manors
题意：有ｎ个人，每个人占据ｍ个点，每个人所属区域是该区域内的点到自己控制的点的距离小于其他人．
化简一下题目给的式子，得到直线方程，半平面交求解即可～
1 #include <bits/stdc++.h> 2 using namespace std; 3 const double pi = acos(-1.0); 4 const int maxn = 110; 5 const int inf = 0x3f3f3f3f; 6 const double eps = 1e-8; 7 struct Point { 8 double x,y; 9 Point (double x = 0, double y = 0) : x(x), y(y) {} 10 }; 11 typedef Point Vector; 12 Vector operator + (Vector a, Vector b) { 13 return Vector (a.x + b.x, a.y + b.y); 14 } 15 Vector operator * (Vector a, double s) { 16 return Vector (a.x * s, a.y * s); 17 } 18 Vector operator / (Vector a, double p) { 19 return Vector (a.x / p, a.y / p); 20 } 21 Vector operator - (Point a, Point b) { 22 return Vector (a.x - b.x, a.y - b.y); 23 } 24 bool operator < (Point a, Point b) { 25 return a.x < b.x || (a.x == b.x && a.y < b.y); 26 } 27 int dcmp (double x) { 28 if(fabs(x) < eps) return 0; 29 return x < 0 ? -1 : 1; 30 } 31 bool operator == (const Point &a, const Point &b) { 32 return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; 33 } 34 double Dot(Vector a, Vector b) { 35 return a.x * b.x + a.y * b.y; 36 } 37 double Angle(Vector a){ 38 return atan2(a.y, a.x); 39 } 40 double Length(Vector a) { 41 return sqrt(Dot(a, a)); 42 } 43 double Cross (Vector a, Vector b) { 44 return a.x * b.y - a.y * b.x; 45 } 46 //半平面交 47 struct Line { 48 Point p; 49 Vector v; 50 double rad; 51 Line () {} 52 Line (Point p, Vector v) : p(p), v(v) { 53 rad = atan2(v.y, v.x); 54 } 55 bool operator < (const Line &L) const { 56 return rad < L.rad; 57 } 58 }; 59 bool OnLeft(Line L, Point p) { 60 return Cross(L.v, p - L.p) > 0; 61 } 62 Point GetLineIntersection (Line a, Line b) { 63 Vector u = a.p - b.p; 64 double t = Cross(b.v, u) / Cross(a.v, b.v); 65 return a.p + a.v*t; 66 } 67 68 int HalfplaneIntersection(Line *L, int n, Point *poly) { 69 sort(L, L+n); 70 int first,last; 71 Point *p = new Point[n]; 72 Line *q = new Line[n]; //双端队列 73 q[first = last = 0] = L[0]; 74 for(int i = 1; i < n; i++) { 75 while(first < last && !OnLeft(L[i], p[last-1])) last--; //去尾 76 while(first < last && !OnLeft(L[i], p[first])) first++; 77 q[++last] = L[i]; 78 if(dcmp(Cross(q[last].v, q[last-1].v)) == 0) { 79 last--; 80 if(OnLeft(q[last], L[i].p)) q[last] = L[i]; 81 } 82 if(first < last) p[last-1] = GetLineIntersection (q[last-1],q[last]); 83 } 84 while(first < last && !OnLeft(q[first], p[last-1])) last--; //删除无用平面 85 if(last - first <= 1) { 86 delete []p; 87 delete []q; 88 return 0; //空集 89 } 90 p[last] = GetLineIntersection (q[last], q[first]); 91 int m = 0; 92 for(int i = first; i <= last; i++) poly[m++] = p[i]; 93 delete []p; 94 delete []q; 95 return m; 96 } 97 98 double ConvexPolygonArea(Point *p, int n) { 99 double area = 0; 100 for(int i = 1; i < n-1; i++) { 101 area += Cross(p[i] - p[0], p[i+1] - p[0]); 102 } 103 return area / 2; 104 } 105 double X[maxn], Y[maxn], FX[maxn], FY[maxn]; 106 Point poly[maxn], p1[6]; 107 Line line[maxn]; 108 int main(){ 109 //freopen("in.txt", "r", stdin); 110 int t, kase = 0; 111 scanf("%d", &t); 112 while(t--){ 113 int n, m; 114 scanf("%d %d", &n, &m); 115 double x, y; 116 for(int i = 0; i < n; i++){ 117 X[i] = Y[i] = FX[i] = FY[i] = 0; 118 for(int j = 0; j < m; j++){ 119 scanf("%lf %lf", &x, &y); 120 X[i] += x; 121 Y[i] += y; 122 FX[i] += x*x; 123 FY[i] += y*y; 124 } 125 } 126 int cnt = 0; 127 p1[0] = Point(0, 4095); p1[1] = Point(0, 0); 128 p1[2] = Point(4095, 0); p1[3] = Point(4095, 4095); 129 printf("Case #%d:", ++kase); 130 for(int i = 0 ; i < n; i++){ 131 cnt = 0; 132 for(int j = 0; j < n; j++) if(i!=j){ 133 double a = 2 * (X[i] - X[j]); 134 double b = 2 * (Y[i] - Y[j]); 135 double c = FX[j] + FY[j] - FX[i] - FY[i]; 136 Vector v = Vector(b, -a); 137 Point p; 138 if(fabs(a) > fabs(b)) p = Point(-c/a, 0); 139 else p = Point(0, -c/b); 140 line[cnt++] = Line(p, v); 141 } 142 for(int i = 0; i < 4; i++){ 143 line[cnt++] = Line(p1[i], p1[(i+1)%4] - p1[i]); 144 } 145 int sz = HalfplaneIntersection(line, cnt, poly); 146 double ans = ConvexPolygonArea(poly, sz); 147 printf(" %d", int(ans+0.5)); 148 } 149 puts(""); 150 } 151 return 0; 152 }