solution-code2050

2018-06-25

lolifamily

相信大家一眼就看出是二分答案的模板题，问题就是如何检验是否可行。

我们先求出最小的能够包含所有点的矩形，暴力选取四个角分别覆盖，再这样操作一次，检验最后一个矩形的大小就可以了。

注意覆盖完成后要恢复到初始状态！！

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define inf 0x3F3F3F3F
6
using namespace std;
7
struct Node
8
{
9
  int x,y;
10
  bool cover[2];
11
}a[20005];
12
struct Rectangle
13
{
14
  int x1,y1,x2,y2;
15
};
16
int n;
17
inline Rectangle get()
18
{
19
  Rectangle rec;
20
  rec.x1=rec.y1=inf;
21
  rec.x2=rec.y2=-inf;
22
  for(int i=1;i<=n;++i)
23
  {
24
    if(a[i].cover[0]||a[i].cover[1])continue;
25
    rec.x1=min(rec.x1,a[i].x);
26
    rec.y1=min(rec.y1,a[i].y);
27
    rec.x2=max(rec.x2,a[i].x);
28
    rec.y2=max(rec.y2,a[i].y);
29
  }
30
  return rec;
31
}
32
inline void cover(int x,int y,int len,int index,bool flag)
33
{
34
  int i;
35
  for(i=1;i<=n;++i)
36
  {
37
    if(a[i].x>=x&&a[i].x<=x+len&&a[i].y>=y&&a[i].y<=y+len)a[i].cover[index]=flag;
38
  }
39
  return;
40
}
41
inline void cover(Rectangle rec,int limit,int corner,int index,bool flag)
42
{
43
  if(corner==1)cover(rec.x1,rec.x2,limit,index,flag);
44
  if(corner==2)cover(rec.x2-limit,rec.y1,limit,index,flag);
45
  if(corner==3)cover(rec.x1,rec.y2-limit,limit,index,flag);
46
  if(corner==4)cover(rec.x2-limit,rec.y2-limit,limit,index,flag);
47
  return;
48
}
49
inline bool check(int limit)
50
{
51
  int i,j;
52
  for(i=1;i<=n;++i)a[i].cover[0]=a[i].cover[1]=false;
53
  Rectangle rec1=get();
54
  for(i=1;i<=4;++i)
55
  {
56
    cover(rec1,limit,i,0,true);
57
    Rectangle rec2=get();
58
    for(j=1;j<=4;++j)
59
    {
60
      cover(rec2,limit,j,1,true);
61
      Rectangle rec3=get();
62
      if(max(rec3.x2-rec3.x1,rec3.y2-rec3.y1)<=limit)return true;
63
      cover(rec2,limit,j,1,false);
64
    }
65
    cover(rec1,limit,i,0,false);
66
  }
67
  return false;
68
}
69
int main(void)
70
{
71
  freopen("2050.in","r",stdin);
72
  int i,L,R,mid;
73
  scanf("%d",&n);
74
  for(i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y);
75
  Rectangle rec=get();
76
  L=0;R=max(rec.x2-rec.x1,rec.y2-rec.y1);
77
  while(L<R)
78
  {
79
    mid=(L+R)>>1;
80
    if(check(mid))R=mid;
81
    else L=mid+1;
82
  }
83
  printf("%d\n",L);
84
  return 0;
85
}