重剑无锋
我生待明日,万事成蹉跎
posts - 13,  comments - 6,  trackbacks - 0
这个主要是线段相交的处理,完全按照算法导论写一下几何就好了。并查集不想再说了。
叉积是好东西,同学们必须学会。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<iomanip>
  5 using namespace std;
  6 const int maxnum=1000+1;
  7 #define rep(i,n,m) for(int i=(n);i<=(m);++i)
  8 #define re1(i,n) rep(i,1,n)
  9 struct point{
 10     double x,y;
 11     point(){
 12 
 13     }
 14     point(double  x,double y):x(x),y(y){
 15 
 16     }
 17     friend ostream& operator<<(ostream &out,point a){
 18         out<<'('<<a.x<<','<<a.y<<')';
 19         return out;
 20     }
 21 };
 22 struct seg{
 23     double x,y;
 24     point from,to;
 25     seg(){
 26 
 27     }
 28     seg(point a,point b):from(a),to(b){
 29         double x1=a.x,x2=b.x;
 30         double y1=a.y,y2=b.y;
 31         x=x2-x1;
 32         y=y2-y1;
 33     }
 34 };
 35 double cross(seg a,seg b){
 36     double x1=a.x,x2=b.x;
 37     double y1=a.y,y2=b.y;
 38     return x1*y2-y1*x2;
 39 }
 40 double cross(point p0,point p1,point p2){
 41     return cross(seg(p0,p1),seg(p0,p2));
 42 }
 43 bool between(double a,double b,double x){
 44     return x>=&& x<=b;
 45 }
 46 bool on_seg(point p1,point p2,point p0){
 47     double x1=p1.x,x2=p2.x;
 48     double y1=p1.y,y2=p2.y;
 49     return between(min(x1,x2),max(x1,x2),p0.x) && between(min(y1,y2),max(y1,y2),p0.y);
 50 }
 51 bool intersect(point p1,point p2,point p3,point p4){
 52     int d1=cross(p3,p4,p1);
 53     int d2=cross(p3,p4,p2);
 54     int d3=cross(p1,p2,p3);
 55     int d4=cross(p1,p2,p4);
 56     if(((d1>0 && d2<0)||(d1<0 && d2>0)) &&((d3>0 && d4<0||(d3<0 && d4>0)))
 57         return true;
 58     else if(d1==0 && on_seg(p3,p4,p1))
 59         return true;
 60     else if(d2==0 && on_seg(p3,p4,p2))
 61         return true;
 62     else if(d3==0 && on_seg(p1,p2,p3))
 63         return true;
 64     else if(d4==0 && on_seg(p1,p2,p4))
 65         return true;
 66     else 
 67         return false;
 68     
 69 }
 70 struct seg segs[maxnum];
 71 int G[maxnum];
 72 int num[maxnum];
 73 int find(int x){
 74     if(G[x]!=x)
 75         G[x]=find(G[x]);
 76     return G[x];
 77 }
 78 void u3n(int a,int b){
 79     int x=find(a);
 80     int y=find(b);
 81     if(x==y)
 82         return;
 83     G[x]=y;
 84     num[y]+=num[x];
 85 }
 86 void showline(int n,int m){
 87     rep(i,n,m){
 88         cout<<setw(6)<<i;
 89     }
 90     cout<<endl<<endl;
 91 }
 92 template<class T>
 93 void show(T *a,int n,int m){
 94     rep(i,n,m){
 95         cout<<setw(6)<<a[i];
 96     }
 97     cout<<endl;
 98 }
 99 int main(){    
100     int tcase;
101     scanf("%d",&tcase);
102     while(tcase--){
103         int m,n=0;
104         scanf("%d",&m);
105         char cmd[2];
106         re1(u,m){
107             G[u]=u;
108             num[u]=1;
109         }
110         re1(u,m){
111             scanf("%s",cmd);
112             if(cmd[0]=='P'){
113                 double x1,y1,x2,y2;
114                 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
115                 segs[++n]=seg(point(x1,y1),point(x2,y2));        
116         //        cout<<segs[n].from<<' '<<segs[n].to<<endl;
117                 re1(i,n-1){
118                     if(intersect(segs[i].from,segs[i].to,segs[n].from,segs[n].to))
119                         u3n(i,n);
120                 }
121             }else{
122                 int id;
123                 scanf("%d",&id);
124                 printf("%d\n",num[find(id)]);
125             }
126         }
127         //showline(1,6);
128         //show(G,1,6);
129         //show(num,1,6);
130         if(tcase)
131             printf("\n");
132     }
133 }
posted on 2012-12-10 21:31 Gin 阅读(423) 评论(0)  编辑 收藏 引用 所属分类: Data Structure

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿

随笔分类

随笔档案

friends

  • figoSB
  • 除了我...谁敢叫韩飞sb...

搜索

  •  

最新评论

阅读排行榜

评论排行榜