首页 > 代码库 > hdu 1558 Segment set【基础带权并查集+计算几何】

hdu 1558 Segment set【基础带权并查集+计算几何】

2024-11-28 00:31:02   205人阅读

Segment set

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


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
1
2
2
2
5

分析：这道题是道基础带权并查集的题，主要就是如何判断两条线段相交（注意：是线段）

有一个链接：http://blog.csdn.net/rickliuxiao/article/details/6259322

为了确定两条线段是否相交，要检查每个线段是否跨越了包含另一线段的直线。 给定一个线段p1p2,如果点p1位于某一直线的一边， 而点p2位于直线的另一边，则称线段p1p2跨越了该直线。如果p1和p2 就落在该直线的话，即出现边界情况。两条线段相交， 当且仅当下面两个条件中有一个成立，或同时成立：

1)每个线段都跨越包含了另一线段的直线。

2)一个线段的某一端点位于另一线段上。

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. #include<iostream>
  5. #define Min(a,b) a<b?a:b
  6. #define Max(a,b) a>b?a:b
  7. #define maxh 1000+10
  8. using namespace std;
  9. typedef struct{
  10.     double x,y;
  11. }point;
  12. typedef struct{
  13.     point p0,p1;
  14. }node;
  15. node E[maxh];
  16. int set[maxh],rank[maxh];
  17. void init(){
  18.     for(int i=0;i<maxh;i++){
  19.         set[i]=i,rank[i]=1;
  20.     }
  21. }
  22. int findx(int x){
  23.     if(x==set[x])
  24.     return x;
  25.     set[x]=findx(set[x]);
  26.     return set[x];
  27. }
  28. void Union(int x,int y){
  29.     x=findx(x);
  30.     y=findx(y);
  31.     if(x!=y){
  32.         set[x]=y;
  33.         rank[y]+=rank[x];
  34.     }
  35. }
  36. double direction(point p0,point p1,point p2){
  37.     return ((p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y));
  38. }
  39. bool on(point p0,point p1,point p2){
  40.     double xmin,ymin,xmax,ymax;
  41.     xmin=Min(p0.x,p1.x);
  42.     xmax=Max(p0.x,p1.x);
  43.     ymin=Min(p0.y,p1.y);
  44.     ymax=Max(p0.y,p1.y);
  45.     if(p2.x>=xmin&&p2.x<=xmax&&p2.y>=ymin&&p2.y<=ymax)
  46.     return true;
  47.     return false;
  48. }
  49. bool intersect(point p0,point p1,point p2,point p3){
  50.     double d0,d1,d2,d3;
  51.     d0=direction(p2,p3,p0);
  52.     d1=direction(p2,p3,p1);
  53.     d2=direction(p0,p1,p2);
  54.     d3=direction(p0,p1,p3);
  55.   //  printf("%lf %lf %lf %lf\n",d0,d1,d2,d3);
  56.     if(((d0<0&&d1>0)||(d0>0&&d1<0))&&((d2>0&&d3<0)||(d2<0&&d3>0))){
  57.     //    printf("cwefg");
  58.     return true;
  59.     }
  60.     else if(d0==0&&on(p2,p3,p0))
  61.     return true;
  62.     else if(d1==0&&on(p2,p3,p1))
  63.     return true;
  64.     else if(d2==0&&on(p0,p1,p2))
  65.     return true;
  66.     else if(d3==0&&on(p0,p1,p3))
  67.     return true;
  68.     else
  69.     return false;
  70. }
  71. int main(){
  72.     int T,n,h,x;
  73.     char c[2];
  74.     scanf("%d",&T);
  75.     while(T--){
  76.         scanf("%d",&n);
  77.         init();
  78.         h=1;
  79.         while(n--){
  80.             scanf("%s",c);
  81.             if(c[0]==‘P‘){
  82.                 scanf("%lf%lf%lf%lf",&E[h].p0.x,&E[h].p0.y,&E[h].p1.x,&E[h].p1.y);
  83.                 for(int i=1;i<h;i++){
  84.                     if(intersect(E[i].p0,E[i].p1,E[h].p0,E[h].p1)){
  85.                    //     printf("<%d,%d>\n",i,h);
  86.                         Union(i,h);
  87.                     }
  88.                 }
  89.                 h++;
  90.             }
  91.             else{
  92.                 scanf("%d",&x);
  93.                 printf("%d\n",rank[findx(x)]);
  94.             }
  95.         }
  96.         if(T){
  97.             printf("\n");
  98.         }
  99.     }
  100.     return 0;
  101. }
  102.                     
  103.     


hdu 1558 Segment set【基础带权并查集+计算几何】


联系
我们