Problem E: Hotter Colder
The children's game Hotter Colder is played as follows. Player A leaves the room while player B hides an object somewhere in the room. Player A re-enters at position (0,0) and then visits various other positions about the room. When player A visits a new position, player B announces "Hotter" if this position is closer to the object than the previous position; player B announces "Colder" if it is farther and "Same" if it is the same distance. Input consists of up to 50 lines, each containing an x,y coordinate pair followed by "Hotter", "Colder", or "Same". Each pair represents a position within the room, which may be assumed to be a square with opposite corners at (0,0) and (10,10). For each line of input print a line giving the total area of the region in which the object may have been placed, to 2 decimal places. If there is no such region, output 0.00.
Sample Input
10.0 10.0 Colder 10.0 0.0 Hotter 0.0 0.0 Colder 10.0 10.0 Hotter
Output for Sample Input
50.00 37.50 12.50 0.00
目明：平面上有一不知道的在哪的(x, y)
玩家A(0,0)出，然後玩家A走到下一 (nx, ny)，
玩家B跟A他上一走的 (lx, ly)，
哪(x,y) 比近，如果是 Hotter 代表 (nx, ny) 比近，反之 (lx, ly)
如果是 Same 的，直接出 0.000 直至最後。
目分析：是一半平面交的， (nx, ny) (lx, ly) 做中垂，
然後用中垂多形一劈半，保留其中的一，
如果是 Hotter 保留 (nx, ny) 同的那，反之 (lx, ly)。
#include <stdio.h>
#include <math.h>
#include <string.h>
struct Pt {
double x, y;
};
struct Polygon {
Pt p[505];
int n;
};
double calcArea(Polygon &p) {
static int i;
double sum = 0;
p.p[p.n] = p.p[0];
for(i = 0; i < p.n; i++)
sum += p.p[i].x*p.p[i+1].y - p.p[i].y*p.p[i+1].x;
return fabs(sum/2);
}
void print(Polygon &p) {
for(int i = 0; i < p.n; i++)
printf("%lf %lf\n", p.p[i].x, p.p[i].y);
puts("=====");
}
int main() {
int n, w = 10, h = 10;
int i, j, k;
double sx, sy, ex, ey, xi, yi;
char cmd[50];
Polygon A, B, C;
A.n = 4;
A.p[0].x = 0, A.p[0].y = 0;
A.p[1].x = w, A.p[1].y = 0;
A.p[2].x = w, A.p[2].y = h;
A.p[3].x = 0, A.p[3].y = h;
sx = 0, sy = 0;
while(scanf("%lf %lf", &ex, &ey) == 2) {
scanf("%s", cmd);
// ax + by + c = 0
double a, b, c;
#define eps 1e-8
double m = -(sy-ey)/(sx-ex);
a = sx-ex, b = sy-ey;
c = -(a*((sx+ex)/2)+b*((sy+ey)/2));
//printf("%lf x + %lf y + %lf = 0\n", a, b, c);
A.p[A.n] = A.p[0];
B.n = 0, C.n = 0;
Pt intP[2];
int point = 0;
for(i = 0; i < A.n; i++) {
if(point == 1) {
if(B.n == 0 || fabs(B.p[B.n-1].x-A.p[i].x) > eps ||
fabs(B.p[B.n-1].y-A.p[i].y) > eps)
B.p[B.n++] = A.p[i];
} else {
if(C.n == 0 || fabs(C.p[C.n-1].x-A.p[i].x) > eps ||
&nsp; fabs(C.p[C.n-1].y-A.p[i].y) > eps)
C.p[C.n++] = A.p[i];
}
//printf("(%lf %lf)-(%lf %lf)\n", A.p[i].x, A.p[i].y, A.p[i+1].x, A.p[i+1].y);
if((a*A.p[i].x+b*A.p[i].y+c)*(a*A.p[i+1].x+b*A.p[i+1].y+c) <= eps) {
if(point == 2) continue;
double ta, tb, tc;
double tm = (A.p[i].y-A.p[i+1].y)/(A.p[i].x-A.p[i+1].x);
if(fabs(A.p[i].x-A.p[i+1].x) < eps)
ta = 1, tb = 0, tc = -A.p[i].x;
else
ta = tm, tb = -1, tc = -(A.p[i].x*ta+A.p[i].y*tb);
// ax+by+c = 0, ta*x+tb*y+tc = 0
//printf("%lf x + %lf y + %lf = 0\n", ta, tb, tc);
double rx, ry, r;
r = a*tb-ta*b;
rx = (-c)*tb-(-tc)*b;
ry = a*(-tc)-ta*(-c);
rx = rx/r;
ry = ry/r;
if(fabs(r) < eps) continue; // no intersection
if(point == 1) {
if(fabs(rx-intP[0].x) < eps && fabs(ry-intP[0].y) < eps)
continue;
}
//printf("intersection %lf %lf\n", rx, ry);
intP[point].x = rx, intP[point].y = ry;
if(B.n == 0 || fabs(B.p[B.n-1].x-rx) > eps || fabs(B.p[B.n-1].y-ry) > eps)
B.p[B.n++] = intP[point];
if(C.n == 0 || fabs(C.p[C.n-1].x-rx) > eps || fabs(C.p[C.n-1].y-ry) > eps)
C.p[C.n++] = intP[point];
point++;
}
}
if(point != 2) {
printf("%.2lf\n", calcArea(A));
sx = ex, sy = ey;
continue;
}
int f1, f2;
f1 = (a*B.p[B.n/2].x + b*B.p[B.n/2].y + c) < eps;
if(!strcmp("Same", cmd))
A.n = 0, B.n = 0, C.n = 0;
else if(!strcmp("Hotter", cmd))
xi = ex, yi = ey;
else
xi = sx, yi = sy;
f2 = (a*xi + b*yi + c) < eps;
if(f1 == f2 && point) {// same side
//puts("B side");
A = B;
} else {
//puts("C side");
A = C;
}
while(fabs(A.p[A.n-1].x-A.p[0].x) < eps &&
fabs(A.p[A.n-1].y-A.p[0].y) < eps)
A.n--;
//print(A);
printf("%.2lf\n", calcArea(A));
sx = ex, sy = ey;
}
return 0;
}
文章定位：
