1052: [HAOI2007]覆盖问题 - #include <Seter> - using namespace Orz;
1052: [HAOI2007]覆盖问题
http://www.zybbs.org/JudgeOnline/problem.php?id=1052
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 145744 | Seter | 1052 | Accepted | 952 kb | 88 ms | C/Edit | 1472 B | 2011-08-24 10:41:35 |
为了R1用小号刷了14次……还加了个cheat（就是我不知道对不对的优化）……我知道被很多人BS了……
枚举+判定。先卡出一个矩形，然后证明三个正方形至少有一个在这个矩形的角上。考虑用一个矩形卡住符合条件的三个正方形，这个矩形肯定能卡住所有点，也肯定是最小的。如果没有一个正方形在角上，那么由于矩形有四条边，必定有两个正方形横跨两对对边，那么矩形两边长必定都等于正方形边长，然后还是卡在角上……
于是就可以枚举第一个正方形在哪个角上，删掉那些点，再枚举第二个正方形在哪个角上……
提示：找不出错误的时候可以考虑REWRITE……我N天前WA无数次这题，昨天又看到这题，REWRITE一次十来分钟就AC了……
CHEAT：第二个正方形所在的角可以从前一个正方形所在的角的后面开始枚举……也就是枚举12,13,14,23,24,34六对角就可以了……这个是对的么？WSMDBZD……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <stdio.h>#define max(x,y) ((x)>(y)?(x):(y))#define dis(x) ((x)>0?(x):-(x))#define init(i) b[i][0].x=b[i][0].y=-1000000000;b[i][1].x=b[i][1].y=1000000000#define update(j,i) if(b[j][0].x<a[i].x)b[j][0].x=a[i].x;\ if(b[j][1].x>a[i].x)b[j][1].x=a[i].x;\ if(b[j][0].y<a[i].y)b[j][0].y=a[i].y;\ if(b[j][1].y>a[i].y)b[j][1].y=a[i].yshort n,d[20000],ds,i,j,k,x1,x2,ch,k;int re,l,r,mid;struct point{int x,y;}a[20000],b[3][2];__inline getint(){ for(re=0,ch=getchar();ch!='-'&&(ch<'0'||ch>'9');)if((ch=getchar())<=0)return -1; for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?-re:re;}__inline short check(l){ for(j=0;j<3;j++){ x1=j>>1;x2=j&1;init(1); for(ds=i=0;i<n;i++)if(dis(b[0][x1].x-a[i].x)>l||dis(b[0][x2].y-a[i].y)>l){d[ds++]=i;update(1,i);} if(b[1][0].x-b[1][1].x<=l&&b[1][0].y-b[1][1].y<=l)return 1; for(k=j+1;k<4;k++){ x1=k>>1;x2=k&1;init(2); for(i=0;i<ds;i++)if(dis(b[1][x1].x-a[d[i]].x)>l||dis(b[1][x2].y-a[d[i]].y)>l){update(2,d[i]);} if(b[2][0].x-b[2][1].x<=l&&b[2][0].y-b[2][1].y<=l)return 1; } }return 0;}main(){ int i;init(0); for(i=n=getint();i;){ a[--i].x=getint(); a[i].y=getint(); update(0,i); }for(l=0,r=max(b[0][0].x-b[0][1].x,b[0][0].y-b[0][1].y),mid=r>>1;l+1!=r;mid=l+r>>1)check(mid)?(r=mid):(l=mid); printf("%d\n",r); return 0;} |
By Seter
评论 (0)