pku 3943 Digits on the Floor 并查集的活用(重点)+数字识别

题意很简单,给出一些线段,组成一些数字,保持数字连接点的联通关系不变(就说是图的逻辑结构不变吧),并且保证没有相交。要求识别数字。
首先这题,涉及到并查集的运用。开始犯了个很糊涂的错误,本题新加上一条线段可能造成2种情况
1、A - C,新加线为C,就是把C连接到某个树枝上
2、A-C-B,这种情况考虑漏了,就是通过C这个线把俩个不连通的集合给打通了
具体代码应该是这样
for(int j=0;j<now;j++)
    if(find(now)!=find(j)&&cross(now,j))
          set[find(now)]=find(j);
开始糊涂蛋的写成了
for(int j=0;j<now;j++)
      if(cross(now,j))
         set[now]=find(j),break;
这个就是只考虑了第一种情况。

关于数字识别的问题就好办多了,主要根据部分相交和点相交的数目以及联通集中线段的数目来判断数字(5和2还要根据叉积再来弄下),这题受益最深的就是并查集那里,容易犯的错误。

代码如下:
  1 Source Code
  2 
  3 Problem: 3943        User: yzhw
  4 Memory: 656K        Time: 188MS
  5 Language: G++        Result: Accepted
  6 Source Code
  7 # include <cstdio>
  8 # include <vector>
  9 # include <cstring>
 10 # include <map>
 11 using namespace std;
 12 # define N 1005
 13 # define min(a,b) ((a)<(b)?(a):(b))
 14 # define max(a,b) ((a)>(b)?(a):(b))
 15 struct line
 16 {
 17     int x1,y1,x2,y2;
 18 }l[N];
 19 bool in(int x,int y,const line &pos)
 20 {
 21     if(x>=min(pos.x1,pos.x2)&&x<=max(pos.x1,pos.x2)&&
 22        y>=min(pos.y1,pos.y2)&&y<=max(pos.y1,pos.y2)&&
 23        (pos.y2-pos.y1)*(pos.x2-x)==(pos.x2-pos.x1)*(pos.y2-y))
 24        return true;
 25     else return false;
 26 }
 27 int cross(const line &a,const line &b)
 28 {
 29     if(a.x1==b.x1&&a.y1==b.y1||
 30         a.x2==b.x1&&a.y2==b.y1||
 31         a.x1==b.x2&&a.y1==b.y2||
 32         a.x2==b.x2&&a.y2==b.y2) return 1;
 33     else if(in(a.x1,a.y1,b)||in(a.x2,a.y2,b)||in(b.x1,b.y1,a)||in(b.x2,b.y2,a)) return 2;
 34     else return 0;
 35 }
 36 int cross(int x1,int y1,int x2,int y2)
 37 {
 38     return x1*y2-x2*y1;
 39 }
 40 struct node
 41 {
 42     vector<line> data;
 43     int type() const
 44     {
 45         int num[3]={0,0,0};
 46         for(int i=0;i<data.size();i++)
 47             for(int j=i+1;j<data.size();j++)
 48                 num[cross(data[i],data[j])]++;
 49         if(num[1]==4&&num[2]==0)
 50         {
 51             if(data.size()==4) return 0;
 52             else
 53             {
 54                 int target=-1,x1,y1,x2,y2;
 55                 for(int i=0;i<data.size();i++)
 56                 {
 57                     bool flag=true;
 58                     for(int j=0;j<data.size()&&flag;j++)
 59                         if(j!=i&&(data[i].x1==data[j].x1&&data[i].y1==data[j].y1||data[i].x1==data[j].x2&&data[i].y1==data[j].y2))
 60                             flag=false;
 61                     if(flag)
 62                     {
 63                         target=i;
 64                         x1=data[i].x2,y1=data[i].y2;
 65                         x2=data[i].x1,y2=data[i].y1;
 66                         break;
 67                     }
 68                     flag=true;
 69                     for(int j=0;j<data.size()&&flag;j++)
 70                         if(j!=i&&(data[i].x2==data[j].x1&&data[i].y2==data[j].y1||data[i].x2==data[j].x2&&data[i].y2==data[j].y2))
 71                             flag=false;
 72                     if(flag)
 73                     {
 74                         target=i;
 75                         x1=data[i].x1,y1=data[i].y1;
 76                         x2=data[i].x2,y2=data[i].y2;
 77                         break;
 78                     }
 79                 }
 80                 for(int i=0;i<data.size();i++)
 81                     if(i!=target)
 82                     {
 83                         if(data[i].x1==x1&&data[i].y1==y1)
 84                             return cross(data[i].x2-data[i].x1,data[i].y2-data[i].y1,x1-x2,y1-y2)<0?5:2;
 85                         else if(data[i].x2==x1&&data[i].y2==y1)
 86                             return cross(data[i].x1-data[i].x2,data[i].y1-data[i].y2,x1-x2,y1-y2)<0?5:2;
 87                     }
 88             }
 89             printf("wa!\n");
 90             while(true);
 91         }
 92         else if(num[1]==0&&num[2]==0)
 93             return 1;
 94         else if(num[1]==4&&num[2]==0)
 95             return 2;
 96         else if(num[1]==2&&num[2]==1)
 97             return 3;
 98         else if(num[1]==1&&num[2]==1)
 99             return 4;
100         else if(num[1]==4&&num[2]==1)
101             return 6;
102         else if(num[1]==2&&num[2]==0)
103             return 7;
104         else if(num[1]==4&&num[2]==2)
105             return 8;
106         else if(num[1]==3&&num[2]==1)
107             return 9;
108     }
109 };
110 map<int,node> data;
111 int n,set[N],ans[10];
112 int find(int pos)
113 {
114     if(set[pos]==pos) return pos;
115     else return set[pos]=find(set[pos]);
116 }
117 int main()
118 {
119     while(scanf("%d",&n)!=EOF&&n)
120     {
121         data.clear();
122         memset(ans,0,sizeof(ans));
123         for(int i=0;i<n;i++)
124         {
125             set[i]=i;
126             scanf("%d%d%d%d",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
127             for(int j=0;j<i;j++)
128                 if(cross(l[i],l[j])&&find(i)!=find(j))
129                     set[find(i)]=find(j);
130         }
131         for(int i=0;i<n;i++)
132             data[find(i)].data.push_back(l[i]);
133         for(map<int,node>::iterator i=data.begin();i!=data.end();i++)
134             ans[i->second.type()]++;
135         printf("%d",ans[0]);
136         for(int i=1;i<10;i++)
137             printf(" %d",ans[i]);
138         printf("\n");
139     }
140     return 0;
141 }

posted on 2012-01-14 19:57 yzhw 阅读(236) 评论(0)  编辑 收藏 引用 所属分类: data struct


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


<2012年1月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜