URAL - 1966 - Cycling Roads（並查集 + 判線段相交）

URAL - 1966 - Cycling Roads（並查集 + 判線段相交）

題意：n 個點，m 條邊(1 ≤ m < n ≤ 200)，問所有點是否連通（兩條邊相交，則該 4 點連通）。

——>>對於每條邊，邊上的兩端點並入集合，枚舉邊與邊，判斷他們是否相交，是的話各點並入集合，最後看集合內元素的個數是否為n。。

#include 
#include 

const int MAXN = 200 + 10;
const double EPS = 1e-8;

struct POINT
{
    double x;
    double y;

    POINT(){}

    POINT(double x, double y) : x(x), y(y){}
} p[MAXN];

int n, m;
int fa[MAXN], cnt[MAXN];
int u[MAXN], v[MAXN];

typedef POINT Vector;
Vector operator - (Vector A, Vector B)
{
    return Vector(A.x - B.x, A.y - B.y);
}

int Dcmp(double x)
{
    if (fabs(x) < EPS) return 0;
    return x > 0 ? 1 : -1;
}

double Dot(Vector A, Vector B)
{
    return A.x * B.x + A.y * B.y;
}

double Cross(Vector A, Vector B)
{
    return A.x * B.y - A.y * B.x;
}

bool SegmentProperIntersection(POINT a1, POINT a2, POINT b1, POINT b2)
{
    double c1 = Cross(a2 - a1, b1 - a1);
    double c2 = Cross(a2 - a1, b2 - a1);
    double c3 = Cross(b2 - b1, a1 - b1);
    double c4 = Cross(b2 - b1, a2 - b1);
    return Dcmp(c1) * Dcmp(c2) < 0 && Dcmp(c3) * Dcmp(c4) < 0;
}

bool OnSegment(POINT p, POINT a1, POINT a2)
{
    return Dcmp(Cross(a1 - p, a2 - p)) == 0 && Dcmp(Dot(a1 - p, a2 - p)) < 0;
}

void Init()
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        cnt[i] = 1;
    }
}

int Find(int x)
{
    return x == fa[x] ? x : (fa[x] = Find(fa[x]));
}

void Union(int x, int y)
{
    int xroot = Find(x);
    int yroot = Find(y);

    if (xroot != yroot)
    {
        fa[yroot] = xroot;
        cnt[xroot] += cnt[yroot];
    }
}

void Read()
{
    for (int i = 1; i <= n; ++i)
    {
        scanf(%lf%lf, &p[i].x, &p[i].y);
    }
    for (int i = 0; i < m; ++i)
    {
        scanf(%d%d, u + i, v + i);
        Union(u[i], v[i]);
        for (int j = 1; j <= n; ++j)
        {
            if (j != u[i] && j != v[i] && OnSegment(p[j], p[u[i]], p[v[i]]))
            {
                Union(j, u[i]);
            }
        }
    }
}

void Merge()
{
    for (int i = 0; i < m; ++i)
    {
        for (int j = i + 1; j < m; ++j)
        {
            if (SegmentProperIntersection(p[u[i]], p[v[i]], p[u[j]], p[v[j]]))
            {
                Union(u[i], u[j]);
            }
        }
    }
}

void Output()
{
    cnt[Find(1)] == n ? puts(YES) : puts(NO);
}

int main()
{
    while (scanf(%d%d, &n, &m) == 2)
    {
        Init();
        Read();
        Merge();
        Output();
    }

    return 0;
}