POJ 1693

题意：就是给你n条直线，求这n条直线最多可以构成多少个矩形。思路：把直线分类，分成水平的和竖直的，然后两两组合，看是否能构成矩形。枚举12 Memory: 692KTime: 0MS3 Language: G++Result: Accepted4 Source Code5 #include <string.h>6 ...

weixin_30847271

47人浏览 · 2016-06-11 16:06:00

weixin_30847271 · 2016-06-11 16:06:00 发布

题意：就是给你n条直线，求这n条直线最多可以构成多少个矩形。

思路：把直线分类，分成水平的和竖直的，然后两两组合，看是否能构成矩形。枚举

  1 
  2 Memory: 692K		Time: 0MS
  3 Language: G++		Result: Accepted
  4 Source Code
  5 #include <string.h>
  6 #include <stdio.h>
  7 #include <iostream>
  8 
  9 using namespace std;
 10 
 11 int sx,sy,ex,ey;
 12 
 13 struct c{
 14     int sx;
 15     int sy;
 16     int ex;
 17     int ey;
 18 }s[105],h[105];
 19 
 20 
 21 #define judge(x,y) h[y].sx<=s[x].ex&&h[y].ex>=s[x].ex&&s[x].sy<=h[y].ey&&s[x].ey>=h[y].ey
 22 // 目的是判断这两条直线是否有交点。
 23 
 24 
 25 int main()
 26 {
 27     int n,m,nums,ans,numh,tmp;
 28     scanf("%d",&n);
 29     while(n--)
 30     {
 31         scanf("%d",&m);
 32         nums=0,numh=0,ans=0;
 33         for(int i=0;i<m;i++)
 34         {
 35             scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
 36             if(sx==ex)
 37             {
 38                 if(sy>ey){tmp=sy;sy=ey;ey=tmp;}
 39                 s[nums].sx=sx;
 40                 s[nums].sy=sy;
 41                 s[nums].ex=ex;
 42                 s[nums].ey=ey;
 43                 nums++;
 44             }
 45             if(sy==ey)  //对直线进行分类，且这里要注意，直线的起点的坐标不一定要大于终点的坐标。
 46             {
 47                 if(sx>ex){tmp=sx;sx=ex;ex=tmp;}
 48                 h[numh].sx=sx;
 49                 h[numh].sy=sy;
 50                 h[numh].ex=ex;
 51                 h[numh].ey=ey;
 52                 numh++;
 53             }
 54         }
 55             for(int i=0;i<nums;i++)    //每两条直线来比较
 56                 for(int j=0;j<numh;j++)
 57                     if(judge(i,j))
 58                         for(int k=i+1;k<nums;k++)
 59                             if(judge(k,j))
 60                                 for(int l=j+1;l<numh;l++)
 61                                    if(judge(i,l))
 62                                      if(judge(k,l))
 63                                             ans++;
 64             printf("%d\n",ans);
 65     }
 66     return 0;
 67 }
 68 
 69 
 70 
 71 
 72 
 73