ACM模版

描述

题解

计算几何+并查集。神奇的组合……

代码

#include <iostream>

const double eps = 1e-10;
const int MAXN = 1010;

struct point
{
    double x, y;
};

struct edge
{
    point a;
    point b;
};

int pre[MAXN];
int res[MAXN];
struct edge Edge[MAXN];

double min(double a, double b)
{
    return a < b ? a : b;
}

double max(double a, double b)
{
    return a > b ? a : b;
}

bool inter(point a, point b, point c, point d)
{
    if (min(a.x, b.x) > max(c.x, d.x) || min(a.y, b.y) > max(c.y, d.y) || min(c.x, d.x) > max(a.x, b.x) || min(c.y, d.y) > max(a.y, b.y))
    {
        return 0;
    }
    double h, i, j, k;
    h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
    j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
    k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
    return h * i <= eps && j * k <= eps;
}

int find(int x)
{
    int r = x;
    while (pre[r] != r)
    {
        r = pre[r];
    }

    int i = x, j;
    while (i != r)
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void join(int x, int y)
{
    int fx = find(x);
    int fy = find(y);

    if (fx != fy)
    {
        pre[fx] = fy;
        res[fy] += res[fx];
    }

}

int main(int argc, const char * argv[])
{
    int T;
    scanf("%d", &T);

    char order[2];
    int key;
    int n;
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 0; i <= n; i++)
        {
            pre[i] = i;
            res[i] = 1;
        }

        int lines = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", order);
            if (order[0] == 'P')
            {
                lines++;
                scanf("%lf%lf%lf%lf", &Edge[lines].a.x, &Edge[lines].a.y,
                      &Edge[lines].b.x, &Edge[lines].b.y);
                for (int j = 1; j < lines; j++)
                {
                    if (inter(Edge[lines].a, Edge[lines].b, Edge[j].a, Edge[j].b))
                    {
                        join(lines, j);
                    }
                }
            }
            else
            {
                scanf("%d", &key);
                printf("%d\n", res[find(key)]);
            }
        }
        if (T)  // 除了最后一组结尾都要输出空行
        {
            puts("");
        }
    }

    return 0;
}

参考

《判断线段相交》