Description
某人在山上种了N棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄
膜把这些小树遮盖起来，经过一番长久的思考，他决定用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建
立一个平面直角坐标系，设第i棵小树的坐标为（Xi,Yi），3个L*L的正方形的边要求平行与坐标轴，一个点如果在
正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。
Input
第一行有一个正整数N，表示有多少棵树。接下来有N行，第i+1行有2个整数Xi,Yi，表示第i棵树的坐标，保证
不会有2个树的坐标相同。
Output
一行，输出最小的L值。
Sample Input
4
0 1
0 -1
1 0
-1 0
0 1
0 -1
1 0
-1 0
Sample Output
1
HINT
100%的数据，N<=20000
Solution
类似修理牛棚的方法，先用一个大的覆盖全部，然后再逐个用小正方形扣去
这里可以用递归来实现，最多三层，所以时间复杂度
正方形的边长可以二分，总的复杂度即为
不知道为啥我的代码为什么又长又慢。。。
|
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
/************************************************************** Problem: 1052 User: TooDlffcult Language: C++ Result: Accepted Time:2116 ms Memory:3616 kb ****************************************************************/ #include <bits/stdc++.h> using namespace std; const int N = 200005; struct Point { int x,y; }p[N]; int n,Ll,Lr,Lu,Ld,ans,L; int cover[N]; bool work(int Ll,int Lr,int Lu,int Ld,int used) { // if(L == 5) // { // cout << used<<":"; // for(int i = 1; i <= n; ++ i) // cout << cover[i] << " "; // cout << endl; // } if(used == 4) { for(int i = 1; i <= n; ++ i) if(!cover[i]) return false; return true; } int i,a,b,c,d; a = Ll; b = Lr; c = Lu; d = Ld; bool ret = false; //Left Down for(i = 1; i <= n; ++ i) if(p[i].x <= Ll + L && p[i].y <= Ld + L && !cover[i]) cover[i] = used; Ll = Ld = INT_MAX; Lr = Lu = INT_MIN; for(i = 1; i <= n; ++ i) if(!cover[i]) { Ll = min(Ll,p[i].x); Lr = max(Lr,p[i].x); Lu = max(Lu,p[i].y); Ld = min(Ld,p[i].y); } ret |= work(Ll,Lr,Lu,Ld,used+1); Ll = a; Lr = b; Lu = c; Ld = d; for(i = 1; i <= n; ++ i) if(cover[i] == used) cover[i] = 0; //Left Up for(i = 1; i <= n; ++ i) if(p[i].x <= Ll + L && p[i].y >= Lu - L && !cover[i]) cover[i] = used; Ll = Ld = INT_MAX; Lr = Lu = INT_MIN; for(i = 1; i <= n; ++ i) if(!cover[i]) { Ll = min(Ll,p[i].x); Lr = max(Lr,p[i].x); Lu = max(Lu,p[i].y); Ld = min(Ld,p[i].y); } ret |= work(Ll,Lr,Lu,Ld,used+1); Ll = a; Lr = b; Lu = c; Ld = d; for(i = 1; i <= n; ++ i) if(cover[i] == used) cover[i] = 0; //Right Down for(i = 1; i <= n; ++ i) if(p[i].x >= Lr - L && p[i].y <= Ld + L && !cover[i]) cover[i] = used; Ll = Ld = INT_MAX; Lr = Lu = INT_MIN; for(i = 1; i <= n; ++ i) if(!cover[i]) { Ll = min(Ll,p[i].x); Lr = max(Lr,p[i].x); Lu = max(Lu,p[i].y); Ld = min(Ld,p[i].y); } ret |= work(Ll,Lr,Lu,Ld,used+1); Ll = a; Lr = b; Lu = c; Ld = d; for(i = 1; i <= n; ++ i) if(cover[i] == used) cover[i] = 0; //Right Up for(i = 1; i <= n; ++ i) if(p[i].x >= Lr - L && p[i].y >= Lu - L && !cover[i]) cover[i] = used; Ll = Ld = INT_MAX; Lr = Lu = INT_MIN; for(i = 1; i <= n; ++ i) if(!cover[i]) { Ll = min(Ll,p[i].x); Lr = max(Lr,p[i].x); Lu = max(Lu,p[i].y); Ld = min(Ld,p[i].y); } ret |= work(Ll,Lr,Lu,Ld,used+1); Ll = a; Lr = b; Lu = c; Ld = d; for(i = 1; i <= n; ++ i) if(cover[i] == used) cover[i] = 0; return ret; } int main() { int i,l,r; scanf("%d",&n); // if(n <= 3) {printf("1"); return 0;} Ll = Ld = INT_MAX; Lr = Lu = INT_MIN; for(i = 1; i <= n; ++ i) { scanf("%d%d",&p[i].x,&p[i].y); Ll = min(Ll,p[i].x); Lr = max(Lr,p[i].x); Lu = max(Lu,p[i].y); Ld = min(Ld,p[i].y); } l = 0; r = 1<<30; while(l <= r) { L = l + r >> 1; // for(i = 1; i <= n; ++ i) // cout << cover[i] << " "; // cout << endl; if(work(Ll,Lr,Lu,Ld,1)) ans = L, r = L - 1; else l = L + 1; } printf("%d",ans); return 0; } |