做了一波ACM比赛中的题, 感觉计算几何真是奇(luan)妙(tao)无(mu)穷(ban).

这个题是? 挂着期望外衣的计算几何(模板题?)

反正计算几何就是模板在手, 天下我有。

传送门

题目大意各位自己去看吧。

解题报告

乱套一波切割多边形(半平面交?) + 多边形面积的模板, 就过了!

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define pb push_back
typedef double ff;
const ff eps=1e-7;
struct point {
ff x, y; point (ff x=0, ff y=0) :x(x),y(y) {}
point operator + (const point &a) { return point(x+a.x, y+a.y);}
point operator - (const point &a) { return point(x-a.x, y-a.y);}
ff operator *(const point &a) { return x*a.y-y*a.x; }
ff operator ^(const point &a) { return x*a.x+y*a.y; }
point operator *(const ff &a) { return point(x*a, y*a);}
void read() { scanf("%lf%lf", &x,&y);}
void out() { cout<<x<<' '<<y; }
ff len() { return sqrt(x*x+y*y); }
} ;
struct line {
point s, w; line(){}
line (point s, point t) :s(s), w(t-s) {}
} ;
inline ff dists(point p, point a, point b) {
if (abs(b.x-a.x)<eps&&abs(b.y-a.y)<eps) return (p-a).len();
point v1=b-a, v2=p-a, v3=p-b;
if ((v1^v2)<eps) return v2.len();
else if ((v1^v3)>-eps) return v3.len();
else return abs(v1*v2)/v1.len();
}
struct poly {
point p[10]; int n;
poly() { n=0; memset(p,0,sizeof(p)); }
void add(point &v) { p[++n]=v; }
bool in(point P) {
ff x=P.x, y=P.y; bool wn=0; ff k, d1, d2;
for (int i=1;i<=n; ++i) {
if (abs(dists(P,p[i],p[i+1]))<=eps) return 1 ;
k=(p[i+1]-p[i])*(P-p[i]);
d1=p[i].y-P.y, d2=p[i+1].y-P.y;
if (k>eps&&d1<=eps&&d2>eps) wn^=1;
if (k<-eps&&d1>eps&&d2<=eps) wn^=1;
}
return wn;
}
} po;
bool Ins(point a, point b, point c, point d) {
point u=b-a, v=d-c, t1, t2;
if (abs(u*v)<eps) return false;
t1=c-a, t2=d-a; return (u*t1)*(u*t2)<-eps;
}
point GLI(point p, point u, point q, point v) {
point w=p-q; ff t = (v*w)/(u*v);
return p+u*t;
}
poly cutpolygon(poly p, point a, point b) {
point c, d, ip; poly np=poly();
for (int i=1; i<=p.n; ++i) {
c=p.p[i], d=p.p[i+1];
if ((b-a)*(c-a)>-eps) np.add(c);
if (Ins(a,b,c,d)) ip=GLI(a,b-a,c,d-c),np.add(ip);
}
np.p[np.n+1]=np.p[1];
return np;
}
ff area(poly p) {
ff as=0; rep(i,1,p.n) as+=p.p[i]*p.p[i+1]/(ff)2;
return as;
}
int main() {
point a; xep(i,4) a.read(), po.add(a); po.p[5]=po.p[1];
ff as=((ff)4*5*5)/((ff)5*5*5-1)*(ff)5;
as+=area(cutpolygon(po,point(-0.5,-0.5),point(-0.5,0.5)))*(ff)5/((ff)5*5*5-(ff)1*1*1)*(ff)4;
as+=area(cutpolygon(po,point(-0.5,0.5),point(0.5,0.5)))*(ff)5/((ff)5*5*5-(ff)1*1*1)*(ff)6;
as+=area(cutpolygon(po,point(0.5,0.5),point(0.5,-0.5)))*(ff)5/((ff)5*5*5-(ff)1*1*1)*(ff)3;
as+=area(cutpolygon(po,point(0.5,-0.5),point(-0.5, -0.5)))*(ff)5/((ff)5*5*5-(ff)1*1*1);
return printf("%.10lf\n", as),0;
}

留言