UOJ Logo Trinkle的博客

博客

WA爷爷到底有多强?

2017-05-12 17:40:49 By Trinkle

退役后的高三

2016-07-29 10:04:14 By Trinkle

格林公式在面积并问题中的应用

2016-03-21 16:21:58 By Trinkle

或许辛普森积分要成为时代的眼泪了?

格林公式大法好 orzakf

DQxPy=CPdx+Qdy let P=y, Q=x D2dxdy=Cxdyydx

Circle(x0,y0,r):

{x=x0+rcosθy=y0+rsinθ

设边界端点从θ1θ2(逆时针方向)

S=D1dxdy=12Cxdyydx=12θ1θ2(x0+rcosθ)d(y0+rsinθ)(y0+rsinθ)d(x0+rcosθ)=r2θ1θ2[(x0+rcosθ)cosθ+(y0+rsinθ)sinθ]dθ=r2θ1θ2[x0cosθ+y0sinθ+r]dθ=12(f(r,x0,y0,θ2)f(r,x0,y0,θ1))

其中

f(r,x,y,θ)=r2θ+rxsinθrycosθ

所以对于圆并,只要对于每个圆,求出它在最终图形里面所占的边界,然后加起来就好了

复杂度:O(n2log(n))

直线也是类似的,式子还比这个更简单

代码比扫描线短了不少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代码

2015-08-09 16:23:12 By Trinkle

戳我

希望能帮到大家

Rank1已经不再重要

新的征程就在前方

圆的反演

2015-07-11 20:16:47 By Trinkle

Codechef July Challenge 2015 » NTHCIR

虽然我知道在比赛还没结束前挂题解不好,但是还是想骗一发访问量

题目大概是这样的:

有很多圆,满足 Cn(n4)C1,C2,,Cn1 都相切,C3 与 C1,C2 相切,C2 与 C1 相切,图形如下:

现已知 r1,r2,r3,r4,求 rn。询问数<=1000w,n109,时限 1.5s

例如:当 r1=6,r2=r3=3,r4=2 的时候,圆大概长这样:

 

圆的反演是什么呢?

我们先选定一个点 O为反演中心,以 O 为圆心,半径为 r 画一个圆。然后对于平面上的点 PP,如果 PP 在以 O 为起点的射线上,并且 |OP||OP|=r2,那么就说 PP 互为反演点。

所以圆外的点反演一下会到圆内,圆内会到圆外,圆上则不变。

我找了 GeoGebra 来玩玩,效果差不多是长下面这个样子的:

Screenshot%20from%202015-07-11%2018:55:5

反演中心为坐标原点,点 H 在直线上移动,点 J 为射线 AH的焦点,点 I 为点 H 的反演点。

可以看到,一条不过反演中心的直线反演之后变成了一个过反演中心的圆。而且直线和两个圆两两相交。

由于反演的可逆性,这个圆反演一下就变成了一条直线啦~

Screenshot%20from%202015-07-11%2019:04:0

一个不过反演中心的圆反演以后是一个以反演中心位似的圆。

从上面的图来看,显然两个圆是反过来对应的,并不是直接位似。还有切记,圆心反演完以后并不是反演完的圆的圆心,比如上面的点 HI

再来一个好玩点的:

Screenshot%20from%202015-07-11%2019:21:2

抛物线反演一下,不知道变成了什么。。。右边的黑线是 2x,然而不能拟合。

Screenshot%20from%202015-07-11%2019:25:4

然后稍微往下移一点就变成了心型线!

Screenshot%20from%202015-07-11%2019:31:4

椭圆好像跟上面两种差不多,不是太好玩。

Screenshot%20from%202015-07-11%2019:36:1

双曲线反演一下变成了 ...

 

我们不妨把样例反演一下变成下面这样:

Screenshot%20from%202015-07-11%2019:43:5

由于反演前后的几何性质是不会发生改变的,比如反演前两个圆相切,反演完以后他们两个还是相切,只不过可能不是圆与圆相切而是直线与圆相切之类的,因此我们可以像这张图这样建立反演中心,圆 C1,C2 反演完以后就变成了两条直线,而 C3,C4, 反演完之后,由于没过反演中心,所以还是圆;又因为它们都与圆 C1,C2 相切,所以反演以后的圆统统都被夹在了两条直线里面,大小都一样,而且一个挨着一个。

这里详细讲了怎么求一个圆的反演

然而我觉得如果不会求的话,可以随便找圆上的三个点,然后把这三个点反一下,然后再以这三个点画个圆就好了,简单粗暴= =

注意不能直接求圆心。原因在上面第二张截屏。

于是这题的解法已经十分明了了:先把 C1,C2 反成直线,解三角形解出 C3 的位置,然后反成小圆,看一下 C4 塞哪里符合题意,然后就可以 O(1) 求出第 n 个圆反演完以后的圆,直接反回去就好了。

Trinkle Avatar