【BZOJ 1043】【HNOI 2008】下落的圆盘 判断圆相交+线段覆盖

计算几何真的好暴力啊。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define max(a,b) (a) > (b) ? (a) : (b)
#define N 1003
using namespace std;
const double Pi = acos(-1);
inline int dcmp(double x) {return (fabs(x) < 1e-6) ? 0 : (x < 0 ? -1 : 1);}
inline double sqr(double x) {return x * x;}
struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};
struct Rround {
Point O; double R;
Rround(Point _O = Point(0, 0), double _R = 0) : O(_O), R(_R) {}
};
Point operator - (Point a, Point b) {return Point(a.x - b.x, a.y - b.y);}
inline double dis(Rround a, Rround b) {return sqrt(sqr(a.O.x - b.O.x) + sqr(a.O.y - b.O.y));}
inline bool cover(Rround to, Rround now) {return to.R >= now.R + dis(to, now);}
struct Splay {
double l, r;
Splay(double _l = 0, double _r = 0) : l(_l), r(_r) {}
}; Splay s[N];
int n, top;
double ans = 0, tt, nxt;
Rround r[N];
bool pd; inline void ins(Rround a, Rround b) {
double d = dis(a, b), t, st, l;
t = (sqr(a.R) - sqr(b.R) + sqr(d)) / (d + d);
st = atan2((a.O.y - b.O.y), (a.O.x - b.O.x));
//st = atan2((a.O.x - b.O.x), (a.O.y - b.O.y));
l = acos(t / a.R);
s[++top] = Splay(st - l, st + l);
}
inline bool cmp(Splay a, Splay b) {return a.l < b.l;} int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf%lf%lf", &r[i].R, &r[i].O.x, &r[i].O.y); for(int i = 1; i <= n; ++i) {
pd = 0;
for(int j = i + 1; j <= n; ++j)
if (cover(r[j], r[i])) {
pd = 1;
break;
}
if (pd)
continue; top = 0;
for(int j = i + 1; j <= n; ++j)
if (!cover(r[i], r[j]) && r[i].R + r[j].R >= dis(r[i], r[j]))
ins(r[i], r[j]); for(int j = 1; j <= top; ++j) {
if (s[j].l < 0) s[j].l += 2 * Pi;
if (s[j].r < 0) s[j].r += 2 * Pi;
if (s[j].l > s[j].r) {
s[++top] = Splay(0, s[j].r);
s[j].r = 2 * Pi;
}
} sort(s + 1, s + top + 1, cmp); tt = 0; nxt = 0;
for(int j = 1; j <= top; ++j)
if (s[j].l > nxt) {
tt += s[j].l - nxt;
nxt = s[j].r;
} else
nxt = max(nxt, s[j].r);
tt += 2 * Pi - nxt; ans += tt * r[i].R;
} printf("%.3lf\n",ans);
return 0;
}

可惜一开始$π$设为$int$了查了$2h$的错QAQ横坐标相减打错查了$1h+$TWT

上一篇:RunTime的简单使用


下一篇:CentOS 6.5安装jdk1.8