POJ2540-Hotter Colder（半平面交）

100 阅读 0 评论 66 点赞

我是靠谱客的博主柔弱母鸡，这篇文章主要介绍POJ2540-Hotter Colder（半平面交），现在分享给大家，希望可以做个参考。

Hotter Colder

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 2523		Accepted: 1045

Description

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

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).

Output

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

复制代码

1
2
3
4
10.0 10.0 Colder
10.0 0.0 Hotter
0.0 0.0 Colder
10.0 10.0 Hotter

Sample Output

复制代码

题意：在（0,0）到（10,10）的范围内，还在藏在某个点，另一个人从起点出发，每走到一个点，如果离藏匿点近了就是“Hotter”，如果远了就是“Colder”，否则就是“Same”

对于走的每个点，输出可能藏匿的面积大小。

思路：可以转化为 aX+bY+c 与0的大小比较，因此可以用半平面交求解，每次找出中点和中垂线即可。

复制代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(_,a,b) for(int _ = (a); _ < (b); _++)
#define sz(s)  (int)((s).size())
typedef long long ll;
const double eps = 1e-9;
const int maxn = 200;
struct Point{
	double x,y;
	Point(double x=0.0,double y = 0.0):x(x),y(y){}
};
vector<Point> vP;
Point poly[maxn];
typedef Point Vector;
struct Line {
	Point P;
	Vector v;
	double ang;
	Line(){}
	Line(Point P,Vector v):P(P),v(v){
		ang = atan2(v.y,v.x);
	}
	bool operator <(const Line&L) const{
		return ang < L.ang;
	}
};
Line L[maxn];
int lcnt;
Vector operator + (Vector A,Vector B) {
	return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
	return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p){
	return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p){
	return Vector(A.x/p,A.y/p);
}
bool operator < (const Point &a,const Point &b){
	return a.x < b.x || (a.x==a.y && a.y < b.y);
}
int dcmp(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0? -1:1;
}
bool operator == (const Point &a,const Point &b){
	return dcmp(a.x-b.x)==0&& dcmp(a.y-b.y)==0;
}
double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}
double Length(Vector A) {return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B) {return acos(Dot(A,B)/Length(A)/Length(B));}
double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
Vector Rotate(Vector A,double rad) {return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); }
Vector Normal(Vector A) {
	double L = Length(A);
	return Vector(-A.y/L,A.x/L);
}
bool OnLeft(Line L,Point p){
	return Cross(L.v,p-L.P) > 0;
}
Point GetIntersection(Line a,Line b){
	Vector u = a.P-b.P;
	double t = Cross(b.v,u) / Cross(a.v,b.v);
	return a.P+a.v*t;
}
int HalfplaneIntersection(Line* L,int n,Point* poly){
	sort(L,L+n);
	int first,last;
	Point *p = new Point[n];
	Line *q = new Line[n];
	q[first=last=0] = L[0];
	for(int i = 1; i < n; i++){
		while(first < last && !OnLeft(L[i],p[last-1])) last--;
		while(first < last && !OnLeft(L[i],p[first])) first++;
		q[++last] = L[i];
		if(fabs(Cross(q[last].v,q[last-1].v))<eps) {
			last--;
			if(OnLeft(q[last],L[i].P)) q[last] = L[i];
		}
		if(first<last) p[last-1] = GetIntersection(q[last-1],q[last]);
	}
	while(first < last && !OnLeft(q[first],p[last-1])) last--;
	if(last - first <=1) return 0;
	p[last] = GetIntersection(q[last],q[first]);
	int m = 0;
	for(int i = first; i <= last; i++) poly[m++] = p[i];
	return m;
}
void init(){
	vP.clear();
	lcnt = 0;
	vP.push_back(Point(0,0));
	vP.push_back(Point(10,0));
	vP.push_back(Point(10,10));
	vP.push_back(Point(0,10));
	int n = sz(vP);
	#define next(i) ((i)+1)%n
	REP(_,0,n){
		L[_] = Line(vP[_],vP[next(_)]-vP[_]);
		lcnt++;
	}
}
int main(){
	
	double x,y;
	string st;
	init();
	Point pre = Point(0,0),cur;
	bool flag = true;
	while(cin >> x >> y >> st){
		if(!flag){
			printf("0.00n");
			continue;
		}
		cur = Point(x,y);
		if(st[0]=='S'){
			printf("0.00n");
			flag = false;
			continue;
		}else if(st[0]=='H'){
			L[lcnt++] = Line((pre+cur)/2,Normal(pre-cur)) ;
		}else{
			L[lcnt++] = Line((pre+cur)/2,Normal(cur-pre));	
		}
		pre = Point(x,y);
		int m = HalfplaneIntersection(L,lcnt,poly);
		if(m==0){
			printf("0.00n");
			flag = false;
		}else{
			#define next(i) ((i)+1)%m
			double area = 0.0;
			REP(_,0,m) { 
				area += Cross(poly[_],poly[next(_)])/2;
			}
			printf("%.2fn",fabs(area));	
		}
	}	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(_,a,b) for(int _ = (a); _ < (b); _++)
#define sz(s)  (int)((s).size())
typedef long long ll;
const double eps = 1e-9;
const int maxn = 200;
struct Point{
	double x,y;
	Point(double x=0.0,double y = 0.0):x(x),y(y){}
};
vector<Point> vP;
Point poly[maxn];
typedef Point Vector;
struct Line {
	Point P;
	Vector v;
	double ang;
	Line(){}
	Line(Point P,Vector v):P(P),v(v){
		ang = atan2(v.y,v.x);
	}
	bool operator <(const Line&L) const{
		return ang < L.ang;
	}
};
Line L[maxn];
int lcnt;
Vector operator + (Vector A,Vector B) {
	return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
	return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p){
	return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p){
	return Vector(A.x/p,A.y/p);
}
bool operator < (const Point &a,const Point &b){
	return a.x < b.x || (a.x==a.y && a.y < b.y);
}
int dcmp(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0? -1:1;
}
bool operator == (const Point &a,const Point &b){
	return dcmp(a.x-b.x)==0&& dcmp(a.y-b.y)==0;
}
double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}
double Length(Vector A) {return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B) {return acos(Dot(A,B)/Length(A)/Length(B));}
double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
Vector Rotate(Vector A,double rad) {return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); }
Vector Normal(Vector A) {
	double L = Length(A);
	return Vector(-A.y/L,A.x/L);
}
bool OnLeft(Line L,Point p){
	return Cross(L.v,p-L.P) > 0;
}
Point GetIntersection(Line a,Line b){
	Vector u = a.P-b.P;
	double t = Cross(b.v,u) / Cross(a.v,b.v);
	return a.P+a.v*t;
}
int HalfplaneIntersection(Line* L,int n,Point* poly){
	sort(L,L+n);
	int first,last;
	Point *p = new Point[n];
	Line *q = new Line[n];
	q[first=last=0] = L[0];
	for(int i = 1; i < n; i++){
		while(first < last && !OnLeft(L[i],p[last-1])) last--;
		while(first < last && !OnLeft(L[i],p[first])) first++;
		q[++last] = L[i];
		if(fabs(Cross(q[last].v,q[last-1].v))<eps) {
			last--;
			if(OnLeft(q[last],L[i].P)) q[last] = L[i];
		}
		if(first<last) p[last-1] = GetIntersection(q[last-1],q[last]);
	}
	while(first < last && !OnLeft(q[first],p[last-1])) last--;
	if(last - first <=1) return 0;
	p[last] = GetIntersection(q[last],q[first]);
	int m = 0;
	for(int i = first; i <= last; i++) poly[m++] = p[i];
	return m;
}
void init(){
	vP.clear();
	lcnt = 0;
	vP.push_back(Point(0,0));
	vP.push_back(Point(10,0));
	vP.push_back(Point(10,10));
	vP.push_back(Point(0,10));
	int n = sz(vP);
	#define next(i) ((i)+1)%n
	REP(_,0,n){
		L[_] = Line(vP[_],vP[next(_)]-vP[_]);
		lcnt++;
	}
}
int main(){
	
	double x,y;
	string st;
	init();
	Point pre = Point(0,0),cur;
	bool flag = true;
	while(cin >> x >> y >> st){
		if(!flag){
			printf("0.00n");
			continue;
		}
		cur = Point(x,y);
		if(st[0]=='S'){
			printf("0.00n");
			flag = false;
			continue;
		}else if(st[0]=='H'){
			L[lcnt++] = Line((pre+cur)/2,Normal(pre-cur)) ;
		}else{
			L[lcnt++] = Line((pre+cur)/2,Normal(cur-pre));	
		}
		pre = Point(x,y);
		int m = HalfplaneIntersection(L,lcnt,poly);
		if(m==0){
			printf("0.00n");
			flag = false;
		}else{
			#define next(i) ((i)+1)%m
			double area = 0.0;
			REP(_,0,m) { 
				area += Cross(poly[_],poly[next(_)])/2;
			}
			printf("%.2fn",fabs(area));	
		}
	}	
	return 0;
}