題目大意：“更冷更熱”是一個游戲：兩個人在一個左下角與右上角左邊為（0,0)，（10,10)的正方形房間裡，甲閉上眼睛，乙在房間裡藏一個東西。然後甲猜這個東西在哪裡，第一次必須猜（0,0)。第二次開始每猜一個位置乙都要回答“Hotter”， “Colder”， “Same”。
“Hotter”表示新猜的點比上次猜的點要近，“Colder"表示新猜的點比上次猜的點要遠，“Same"表示兩次猜得一樣近。按順序給出甲每次猜的位置乙的回答。依次輸出每次乙回答後所有可能位置的總面積。
思路：對於兩個點A, B。如果有點P到a的距離小於到b的距離，那麼P一定在A，B中垂線靠近A的那一側，反之則在靠近b的一側。如果P到A，B的距離相等，那麼P一定在A，B的中垂線上。由此可以想象每次回答相當於對答案的多邊形做一次切割，也就是求多邊形與半平面的交。每次切割復雜度O（n)
代碼：
#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include
#include #include using namespace std; #define LL long long const double eps = 1e-6; const double pi = acos(-1.0); int cmp(double x) { if(fabs(x) < eps) return 0; if(x > 0)return 1; return -1; } inline double sqr(double x) { return x * x; } struct point { double x, y; point(){} point(double a, double b): x(a), y(b) {} void input(){ scanf("%lf%lf",&x,&y); } friend point operator + (const point &a, const point &b) { return point(a.x + b.x, a.y + b.y); } friend point operator - (const point &a, const point &b) { return point(a.x - b.x, a.y - b.y); } friend bool operator == (const point &a, const point &b) { return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0; } friend bool operator < (const point &a, const point& b) { return cmp(a.x - b.x) < 0 || cmp(a.x - b.x) == 0 && cmp (a.y - b.y) < 0; } friend point operator * (const point &a, const double &b) { return point(a.x * b, a.y * b); } friend point operator * (const double &a, const point &b) { return point(a * b.x, a * b.y); } friend point operator / (const point &a, const double &b) { return point(a.x / b, a.y / b); } double norm(){ return sqrt(sqr(x) + sqr(y)); } }; double det(const point &a, const point &b) { return a.x * b.y - a.y * b.x; } double dot(const point &a, const point &b) { return a.x * b.x + a.y * b.y; } double dist(const point &a, const point &b) { return (a - b).norm(); } double Angle(point a, point b) { if(cmp(dot(a, b) - a.norm() * b.norm()) == 0) return 0; if(cmp(dot(a, b) + a.norm() * b.norm()) == 0) return pi; return acos(dot(a,b) / a.norm() / b.norm()); } double angle(point p) { return atan2(p.y, p.x); } point point_rotate(const point &p, double A){ double tx = p.x, ty = p.y; return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A)); } point point_rotate(const point &p, double sint, double cost) { double tx = p.x, ty = p.y; return point(tx * cost - ty * sint, tx * sint + ty * cost); } struct line { point a, b; line(){} line(point x, point y):a(x),b(y){} void input() { a.input(); b.input(); } }; void point_pro_line(const point p, const point s, const point t, point &cp) { double r = dot(t - s, p - s) / dot (t - s, t - s); cp = s + r * (t - s); } bool point_pro_segment(const point p, const point s, const point t, point &cp) { if(cmp(dot(p - s, t - s))<0) { cp = s; return 0; } if(cmp(dot(p - t, s - t))<0) { cp = t; return 0; } double r = dot(t - s, p - s) / dot (t - s, t - s); cp = s + r * (t - s); return 1; } bool point_on_segment(point p, point s, point t) { return cmp(det(p - s, t - s))== 0 && cmp(dot(p - s, p - t)) < 0; } bool parallel(line a, line b) { return !cmp(det(a.a - a.b, b.a - b.b)); } bool line_cross_line(line a, line b, point &res){ if(parallel(a, b)) return false; double s1 = det(a.a - b.a, b.b - b.a); double s2 = det(a.b - b.a, b.b - b.a); res = (s1 * a.b - s2 * a.a) / (s1 - s2); return true; } int segment_cross_segment(const point& a1,const point& a2,const point& b1,const point& b2, point& res) { double c1 = det(a2 - a1, b1 - a1); double c2 = det(a2 - a1, b2 - a1); double c3 = det(b2 - b1, a1 - b1); double c4 = det(b2 - b1, a2 - b1); if (cmp(c1) * cmp(c2) < 0 && cmp(c3) * cmp(c4) < 0) { res.x = (b1.x * c2 - b2.x * c1) / (c2 - c1); res.y = (b1.y * c2 - b2.y * c1) / (c2 - c1); return 1; } if(point_on_segment(a1, b1, b2)) { res = a1; return 2; } if(point_on_segment(a2, b1, b2)) { res = a2; return 2; } if(point_on_segment(b1, a1, a2)) { res = b1; return 2; } if(point_on_segment(b2, a1, a2)) { res = b2; return 2; } return 0; } int segment_cross_segment(const line& l1, const line& l2, point& res) { point a1 = l1.a, a2 = l1.b, b1 = l2.a, b2 = l2.b; double c1 = det(a2 - a1, b1 - a1); double c2 = det(a2 - a1, b2 - a1); double c3 = det(b2 - b1, a1 - b1); double c4 = det(b2 - b1, a2 - b1); if (cmp(c1) * cmp(c2) < 0 && cmp(c3) * cmp(c4) < 0) { res.x = (b1.x * c2 - b2.x * c1) / (c2 - c1); res.y = (b1.y * c2 - b2.y * c1) / (c2 - c1); return 1; } if(point_on_segment(a1, b1, b2)) { res = a1; return 2; } if(point_on_segment(a2, b1, b2)) { res = a2; return 2; } if(point_on_segment(b1, a1, a2)) { res = b1; return 2; } if(point_on_segment(b2, a1, a2)) { res = b2; return 2; } return 0; } struct polygon { vector P; polygon(int size = 0) { P.resize(size); } point& operator [](int index) { return P[index]; } int size() { return P.size(); } double area() { int n = size(); double sum = 0; for(int i = 0; i < n; i++) sum += det(P[i], P[(i + 1) % n]); return sum * 0.5; } }; polygon polygon_cut(polygon& pol, const point& a, const point& b) { int n = pol.size(); point c, d, p; polygon ret; for(int i = 0; i < n; i++) { c = pol[i]; d = pol[(i + 1) % n]; if(cmp(det(b - a, c - a)) >= 0) ret.P.push_back(c); if(line_cross_line(line(a, b), line(c, d), p)) { if(point_on_segment(p, c, d)) ret.P.push_back(p); } } return ret; } int main() { polygon pol(4); pol[0] = point(0, 0); pol[1] = point(10, 0); pol[2] = point(10, 10); pol[3] = point(0, 10); point p, q = point(0, 0); char str[10]; bool flag = 0; while(scanf("%lf%lf%s", &p.x, &p.y, str) != EOF) { point a = (p + q) / 2; point b = point_rotate(p - q, pi * 0.5) + a; if(str[0] == 'S') flag = 1; if(flag) { puts("0.00"); continue; } if(str[0] == 'C') { pol = polygon_cut(pol, a, b); } else { pol = polygon_cut(pol, b, a); } printf("%.2f\n", fabs(pol.area())); q = p; } return 0; }
