WA爷爷到底有多强?
退役后的高三
退役正好一年了。把回忆录补完。
肯定有退役的oier很疑惑高三该怎么过。希望能帮到大家。
集训队爷就不用D我这个蒟蒻了qaq
http://trinkle.is-programmer.com/2015/7/21/memory.112423.html
广告:https://pan.baidu.com/s/1o8kyBEE 请各位大爷们免费品尝
格林公式在面积并问题中的应用
或许辛普森积分要成为时代的眼泪了?
格林公式大法好 orzakf
设边界端点从
其中
所以对于圆并,只要对于每个圆,求出它在最终图形里面所占的边界,然后加起来就好了
复杂度:
直线也是类似的,式子还比这个更简单
代码比扫描线短了不少2333
BZOJ2178:
/**************************************************************
Problem: 2178
User: wjy1998
Language: C++
Result: Accepted
Time:684 ms
Memory:868 kb
****************************************************************/
#include<cmath>
#include<cstdio>
#include<algorithm>
typedef double ld;
const int N = 1010;
const ld pi = acos(-1);
int n; ld ans;
struct P {
ld x, y;
P operator - (const P&a) const {
return (P) {x - a.x, y - a.y};
}
ld len () {
return sqrt(x * x + y * y);
}
};
struct C {
P o; ld r;
bool operator < (const C&a) const {
if (o.x != a.o.x) return o.x < a.o.x;
if (o.y != a.o.y) return o.y < a.o.y;
return r < a.r;
}
bool operator == (const C&a) const {
return o.x == a.o.x && o.y == a.o.y && r == a.r;
}
ld oint (ld t1, ld t2) {
return r * (r * (t2 - t1) + o.x * (sin(t2) - sin(t1)) - o.y * (cos(t2) - cos(t1)));
}
} a[N];
struct D {
ld x; int c;
bool operator < (const D&a) const {
return x < a.x;
}
} pos[N * 2];
ld work (int c) {
int tot = 0, cnt = 0;
for (int i = 1; i <= n; i++)
if (i != c) {
P d = a[i].o - a[c].o; ld dis = d.len();
if (a[c].r <= a[i].r - dis) return 0;
if (a[i].r <= a[c].r - dis || a[i].r + a[c].r <= dis) continue;
ld g = atan2(d.y, d.x), g0 = acos((dis * dis + a[c].r * a[c].r - a[i].r * a[i].r) / (2 * dis * a[c].r)), l = g - g0, r = g + g0;
if (l < -pi) l += pi * 2;
if (r >= pi) r -= pi * 2;
if (l > r) cnt++;
pos[++tot] = (D) {l, 1};
pos[++tot] = (D) {r, -1};
}
pos[0].x = -pi, pos[++tot].x = pi;
std::sort(pos + 1, pos + 1 + tot);
ld ans = 0;
for (int i = 1; i <= tot; cnt += pos[i++].c)
if (cnt == 0) ans += a[c].oint(pos[i - 1].x, pos[i].x);
return ans;
}
int main () {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf%lf%lf",&a[i].o.x, &a[i].o.y, &a[i].r);
std::sort(a + 1, a + 1 + n);
n = std::unique(a + 1, a + 1 + n) - a - 1;
for (int i = 1; i <= n; i++) ans += work(i);
printf("%.3lf\n", ans / 2);
}
我的BZOJ代码
希望能帮到大家
Rank1已经不再重要
新的征程就在前方
圆的反演
Codechef July Challenge 2015 » NTHCIR
虽然我知道在比赛还没结束前挂题解不好,但是还是想骗一发访问量。
题目大概是这样的:
有很多圆,满足
现已知
例如:当
圆的反演是什么呢?
我们先选定一个点
所以圆外的点反演一下会到圆内,圆内会到圆外,圆上则不变。
我找了
反演中心为坐标原点,点
可以看到,一条不过反演中心的直线反演之后变成了一个过反演中心的圆。而且直线和两个圆两两相交。
由于反演的可逆性,这个圆反演一下就变成了一条直线啦~
一个不过反演中心的圆反演以后是一个以反演中心位似的圆。
从上面的图来看,显然两个圆是反过来对应的,并不是直接位似。还有切记,圆心反演完以后并不是反演完的圆的圆心,比如上面的点
再来一个好玩点的:
抛物线反演一下,不知道变成了什么。。。右边的黑线是
然后稍微往下移一点就变成了心型线!
椭圆好像跟上面两种差不多,不是太好玩。
双曲线反演一下变成了
我们不妨把样例反演一下变成下面这样:
由于反演前后的几何性质是不会发生改变的,比如反演前两个圆相切,反演完以后他们两个还是相切,只不过可能不是圆与圆相切而是直线与圆相切之类的,因此我们可以像这张图这样建立反演中心,圆
然而我觉得如果不会求的话,可以随便找圆上的三个点,然后把这三个点反一下,然后再以这三个点画个圆就好了,简单粗暴= =
注意不能直接求圆心。原因在上面第二张截屏。
于是这题的解法已经十分明了了:先把