USACO 3.4.1 Fence

题目解答

第一个计算几何问题,计算几何问题必须要“踏踏实实”的来,但是也有优化。对于本题目,我使用的是2分法。(我只想到了这个方法,听说还有强大的类似线段树的方法)。首先第一问:使用叉积判断任意两条线段是否绝对相交,若有则输出“NOFENCE”并结束。重点是第二问。观察下图。我们可以很清楚的知道,如果一条线段可以被观察到,他的视野一定不为0,因此,我们只要先找到待观察线段的中点,并与观察点连线就能得到一条新的线段(中位线)。并用新的线段与其它所有线段进行绝对相交判断。同时还要考虑非绝对相交,被点挡住的情况。如果有中位线满足不与所有点相交,那么他一定可以被看到。否则2分。边界条件是两个端点挨在一起了,说明没有满足。这时就要考虑控制精度了。一旦精度过高就会超时。反之就会漏解。(0.005就不错(^o^))具体的实现请看程序。

提一句输出:我们按顺序2分,这样在输出序列里的就是有序的,只是当最后的结点坐标一样时要按输入文件的顺序输出。而只有当第(N-1)与第N个同时要输出时才会不满足(至于为什么不多作解释)。这时先输出N,再输出(N-1)

USACO 3.4.1

运行结果

Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.011 secs, 2940 KB]
Test 2: TEST OK [0.011 secs, 2940 KB]
Test 3: TEST OK [0.000 secs, 2940 KB]
Test 4: TEST OK [0.022 secs, 2940 KB]
Test 5: TEST OK [0.000 secs, 2940 KB]
Test 6: TEST OK [0.054 secs, 2940 KB]
Test 7: TEST OK [0.216 secs, 2940 KB]
Test 8: TEST OK [0.194 secs, 2940 KB]
Test 9: TEST OK [0.194 secs, 2940 KB]
Test 10: TEST OK [0.270 secs, 2940 KB]
Test 11: TEST OK [0.000 secs, 2940 KB]
Test 12: TEST OK [0.011 secs, 2940 KB]
All tests OK.
Your program (‘fence4’) produced all correct answers! This is your
submission #3 for this problem. Congratulations!

程序

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
#include<fstream>
#include<cmath>
using namespace std;
ofstream fout ("fence4.out",ios::out);
ifstream fin ("fence4.in",ios::in);
const double JD = 0.005;
struct Point{
double x,y;
}point[201],see;
struct Line{
Point start,end;
}line[201];
long n,len=0;
bool cansee[201],reg[201];
inline double crossproduct(Point start,Point U,Point V){//计算叉积
double Ux=U.x-start.x,Uy=U.y-start.y,Vx=V.x-start.x,Vy=V.y-start.y;
return (Ux*Vy-Uy*Vx);
}
inline int cancross(Line A,Line B){
double A1=crossproduct(A.start,A.end,B.start),A2=crossproduct(A.start,A.end,B.end),
B1=crossproduct(B.start,B.end,A.start),B2=crossproduct(B.start,B.end,A.end);
if(A1==0 || A2==0) return -1;//被点挡住,A为中位线时,以A为轴,有0就表明被点挡住了.
if(A1*A2<0 && B2*B1<0) return 1;//严格相交
return 0;
}
inline bool check(const Line &mid){
for(int i=1;i<=n;i++) if(!reg[i])
if(cancross(mid,line[i])!=0) return false;
return true;
}
inline bool watch(Point start,Point end){
if(sqrt(((start.x-end.x)*(start.x-end.x))+((start.y-end.y)*(start.y-end.y)))<JD) return false ;
Line mid;//中位线
bool temp= false;
mid.end.x=(start.x+end.x)/2;
mid.end.y=(end.y+start.y)/2;
mid.start.x=see.x;
mid.start.y=see.y;
if(check(mid)) return true ;
else{
temp=watch(start,mid.end);
if(!temp) temp=watch(mid.end,end);
}
return temp;
}
int main()
{
fin>>n>>see.x>>see.y;
fin>>point[1].x>>point[1].y;
for(int i=1;i<=200;i++) cansee[i]= false;
for(int i=2;i<=n;i++){
fin>>point[i].x>>point[i].y;
line[i-1].start=point[i-1];
line[i-1].end=point[i];
}
line[n].start=point[1];
line[n].end=point[n];
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
if(cancross(line[i],line[j])==1){fout<<"NOFENCE"<<endl; return 0;}
for(int i=1;i<=n;i++){
if(crossproduct(see,line[i].start,line[i].end)==0) continue; //cut
reg[i]= true;//不要跟自己比较
if(watch(line[i].start,line[i].end)){len++; cansee[i]=true;}
reg[i]= false;
}
fout<<len<<endl;
if(cansee[n]&&cansee[n-1]){ //如果最后两个都合法,交换
Line temp=line[n];
line[n]=line[n-1];
line[n-1]=temp;
}
for(int i=1;i<=n;i++) if(cansee[i])
fout<<line[i].start.x<< ' '<<line[i].start.y<<' ' <<line[i].end.x<<' '<<line[i].end.y<<endl;
return 0;
}

后记

本文是百度空间的移植,附:全部USACO题目解答