hdu 1558(计算几何+并查集)

Segment set

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4479 Accepted Submission(s): 1672

Problem Description

A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some segment set.

Input

In the first line there is an integer t - the number of test case. For each test case in first line there is an integer n (n<=1000) - the number of commands.

There are two different commands described in different format shown below:

P x1 y1 x2 y2 - paint a segment whose coordinates of the two endpoints are (x1,y1),(x2,y2).
Q k - query the size of the segment set which contains the k-th segment.

k is between 1 and the number of segments in the moment. There is no segment in the plane at first, so the first command is always a P-command.

Output

For each Q-command, output the answer. There is a blank line between test cases.

Sample Input

1
10
P 1.00 1.00 4.00 2.00
P 1.00 -2.00 8.00 4.00
Q 1
P 2.00 3.00 3.00 1.00
Q 1
Q 3
P 1.00 4.00 8.00 2.00
Q 2
P 3.00 3.00 6.00 -2.00
Q 5

Sample Output

题意：求某根线段与其在同一个集合的线段的数量。

题解：线段相交+并查集。。但是我没想清楚为什么按我注释的那样写就WA了。。明明只是顺序不同

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 1005;
struct Point
{
    double x,y;
};
struct Line
{
    Point a,b;
} line[N];
double cross(Point a,Point b,Point c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
bool isCross(Point a, Point b, Point c, Point d)
{
    if (cross(c, b, a)*cross(b, d, a)<0)return false;
    if (cross(a, d, c)*cross(d, b, c)<0)return false;
    return true;
}
int father[N],cnt[N];
int _find(int x)
{
    if(x==father[x]) return x;
    return _find(father[x]);
}
int main()
{
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        int n;
        scanf("%d",&n);
        int k =1;
        for(int i=1; i<=N; i++)
        {
            father[i]=i;
            cnt[i]=1;
        }
        while(n--)
        {
            char c[2];
            scanf("%s",c);
            if(c[0]=='P')
            {
                scanf("%lf%lf%lf%lf",&line[k].a.x,&line[k].a.y,&line[k].b.x,&line[k].b.y);
                k++;
                for(int i=1; i<k; i++)
                {
                    if(isCross(line[i].a,line[i].b,line[k-1].a,line[k-1].b))
                    {
                        int x = _find(k-1);
                        int y = _find(i);
                        if(x!=y)
                        {
                            father[x] = y;
                            cnt[y]+=cnt[x];
                        }
                    }
                }
            }
            if(c[0]=='Q')
            {
                int num;
                scanf("%d",&num);
                /* for(int i=1; i<k; i++) //没想明白
                {
                    if(isCross(line[i].a,line[i].b,line[num].a,line[num].b))
                    {
                        int x = _find(num);
                        int y = _find(i);
                        if(x!=y) {
                            father[x] = y;
                            cnt[y]+=cnt[x];
                        }
                    }
                }*/
                printf("%d
",cnt[_find(num)]);
            }
        }
        if(tcase)
            printf("
");
    }
}