P1302 可见矩形

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1302

题目描述

给定平面上n个互不相交(指公共面积为零)的正方形，它们的顶点坐标均为整数。设坐标原点为O(0, 0)。对于任一正方形R，如果可以找到R的边上2个不同的点A和B，使三角形OAB的内部与其他正方形无公共点，则称正方形R是从O点可见的正方形。

对于给定的n个互不相交的正方形，计算从坐标原点O可见的正方形个数。

输入输出格式

输入格式：

输入文件的第一行是正方形个数n(1≤n≤1000)。

接下来n行中，每行有3个表示正方形的整数X，Y，L。其中，X和Y表示正方形的左下角顶点坐标，L表示边长，1≤X, Y, L≤10000。

输出格式：

输出文件仅有一行包含一个整数，表示从坐标原点O可见的正方形个数。

输入输出样例

输入样例#1：复制

3

2 6 4

1 4 1

2 4 1

输出样例#1：复制

3

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,ans;
   
5. struct square
   
6. {
   
7.     int x,y,l,z;
   
8.     double zs,yx;
   
9. }s[1010];
   
10. bool cmp1(square x,square y)
    
11. {
    
12.     return x.z<y.z;
    
13. }
    
14. bool cmp2(square a,square b)
    
15. {
    
16.     return a.zs>=b.zs;
    
17. }
    
18. int main()
    
19. {
    
20.     cin>>n;
    
21.     for(int i=1;i<=n;i++)
    
22.     {
    
23.         cin>>s[i].x>>s[i].y>>s[i].l;
    
24.         s[i].zs=float(s[i].y+s[i].l)/float(s[i].x);
    
25.         s[i].yx=float(s[i].y)/float(s[i].x+s[i].l);
    
26.         s[i].z=s[i].x+s[i].y+s[i].l;
    
27.     }
    
28.     sort(s+1,s+1+n,cmp1);
    
29.    
    
30.      for(int i=1; i<=n; i++)
    
31.     {
    
32.         sort(s+1,s+i,cmp2);
    
33.         bool flag=1;
    
34.         if(i>=2)
    
35.         {
    
36.             double a=s[1].zs;
    
37.             double b=s[1].yx;
    
38.             for(int j=1; j<i; j++)
    
39.             {
    
40.                 if(s[j].zs>=b)
    
41.                 {
    
42.                         b=min(b,s[j].yx);
    
43.                 }
    
44.                 else
    
45.                 {
    
46.                     if(a>=s[i].zs && b<=s[i].yx)
    
47.                     {
    
48.                         flag=0;
    
49.                         break;
    
50.                     }
    
51.                     a=s[j].zs;
    
52.                     b=s[j].yx;
    
53.                 }
    
54.             }
    
55.             if(a>=s[i].zs && b<=s[i].yx)
    
56.             flag=0;
    
57.         }
    
58.         if(flag)
    
59.             ans++;
    
60.     }
    
61. 
    
62.     cout<<ans<<endl;
    
63.     return 0;
    
64. }

复制代码

吴语林

线段树+离散化

1. #include<cstring>
   
2. #include<iostream>
   
3. #include<cstdio>
   
4. #include<algorithm>
   
5. using namespace std;
   
6. const int maxn=100005;
   
7. bool hash[maxn];
   
8. int cov[maxn<<4];
   
9. double a[maxn*3];
   
10. int cnt;
    
11. struct node
    
12. {
    
13.         double li,ri,z;
    
14. }dian[maxn];
    
15. int BinSea(double key,int n)
    
16. {
    
17.     int l=0,r=n-1;
    
18.     while(l<=r)
    
19.         {
    
20.         int mid=(l+r)/2;
    
21.         if(a[mid]==key) return mid;
    
22.         else if(a[mid]<key) l=mid+1;
    
23.         else r=mid-1;
    
24.     }
    
25.     return -1;
    
26. }
    
27. void Pushdown(int p)
    
28. {
    
29.     if(cov[p]!=-1){
    
30.         cov[p<<1]=cov[p<<1|1]=cov[p];
    
31.         cov[p]=-1;
    
32.     }
    
33. }
    
34. void Update(int p,int l,int r,int x,int y,int c)
    
35. {
    
36.     if(x<=l&&y>=r)
    
37.         {
    
38.         cov[p]=c;
    
39.         return;
    
40.     }
    
41.     Pushdown(p);
    
42.     int mid=(l+r)>>1;
    
43.     if(x<=mid) Update(p<<1,l,mid,x,y,c);
    
44.     if(y>mid) Update(p<<1|1,mid+1,r,x,y,c);
    
45. }
    
46. void Query(int p,int l,int r)
    
47. {
    
48.     if(cov[p]!=-1)
    
49.         {
    
50.         if(!hash[cov[p]])
    
51.                 {
    
52.             cnt++;
    
53.             hash[cov[p]]=true;
    
54.         }
    
55.         return;
    
56.     }
    
57.     if(l==r) return;
    
58.     int mid=(l+r)>>1;
    
59.     Query(p<<1,l,mid);
    
60.     Query(p<<1|1,mid+1,r);
    
61. }
    
62. bool cmp(node x,node y)
    
63. {
    
64.         return x.z>y.z;
    
65. }
    
66. int main()
    
67. {
    
68.     int n,k;
    
69.     scanf("%d",&n);
    
70.     for(int i=0;i<n;i++)
    
71.     {
    
72.             double x,y,lon;
    
73.         scanf("%lf%lf%lf",&x,&y,&lon);
    
74.         dian[i].li=x/(y+lon),dian[i].ri=(x+lon)/y;
    
75.         dian[i].z=x+lon+y;
    
76.         a[k++]=dian[i].li;
    
77.         a[k++]=dian[i].ri;
    
78.         }
    
79.         sort(dian,dian+n,cmp);
    
80.     sort(a,a+k);
    
81.     int h=1;
    
82.     for(int i=1;i<k;i++)
    
83.                 if(a[i]!=a[i-1])
    
84.                         a[h++]=a[i];
    
85.     for(int i=h-1;i>0;i--)
    
86.         if((a[i]-a[i-1])>0.00000000001)
    
87.                         a[h++]=a[i-1]+(a[i]-a[i-1])/2;
    
88.     sort(a,a+h);
    
89.     memset(cov,-1,sizeof(cov));
    
90.     for(int i=0;i<n;i++)
    
91.     {
    
92.         int l=BinSea(dian[i].li,h);
    
93.         int r=BinSea(dian[i].ri,h);
    
94.         Update(1,0,h-1,l,r,i);
    
95.     }
    
96.     cnt=0;
    
97.     memset(hash,false,sizeof(hash));
    
98.     Query(1,0,h-1);
    
99.     printf("%d\n",cnt);
    
100.     return 0;
     
101. }

复制代码

admin

两位做的很认真！方法也是可行的，大家学习下