티스토리 뷰
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8899 에서 채점할 수 있습니다.
풀이 )
1) 문제 지문을 보면 German research group가 아래와 같은 사실이 보장한다고 나옵니다.
There exists a square annulus A of minimum width containing N given points such that its bigger square is a smallest axis-parallel square containing the N points.
이 말에 따르면, 큰 정사각형을 'N개의 점을 모두 포함하는 가장 작은 정사각형' 중에서만 골라도 정답을 찾을 수 있습니다. 'N개의 점을 모두 포함하는 가장 작은 정사각형'의 한 변의 길이는 MAX(max_x-min_x, max_y-min_y) 임은 쉽게 증명할 수 있습니다. 이제 큰 정사각형의 길이는 정해졌습니다. (일단, 일반성을 잃지 않고 max_y-min_y > max_x-min_x 라고 해보겠습니다.)
2) length1 < length2 이고, 크기가 length1인 액자가 N개의 점을 포함할 수 있으면, 크기가 length2인 액자도 N개의 점을 포함 할 수 있습니다. (액자가 length1일 때의 큰 정사각형을 2*(length2-length1)만큼 키우면 되기 때문입니다.)
그러므로 'possible(v) = 액자 크기 v로 N개의 점을 포함하는게 가능한가?' 이와 같은 함수를 완성하면 parametric search로 답을 구할 수 있습니다.
3) 이제 possible(v)를 생각해보겠습니다. 일단 max_y-min_y > max_x-min_x 이므로, 큰 정사각형의 y좌표는 (min_y+max_y)/2 로 고정입니다. 이제 이 상태에서 크기가 v이고, 큰 정사각형의 한 변의 길이는 max_y-min_y인 액자로 N개의 점을 포함할 수 있는 중심 좌표를 찾아보면 됩니다. y좌표는 고정이므로 x좌표만 찾아보면 되지요.
액자 중심의 x좌표의 조건으로는 우선 (max_x-big_square/2 <= 중심의 x <= min_x+big_square/2)를 만족해야 합니다.
(그렇지 않으면 큰 정사각형 밖으로 점이 나갑니다.)
그리고 (min_y + 액자크기 < y < max_y - 액자크기) 를 만족하는 점들의 x에 대해, ( abs(x - 중심의x) >= 작은 정사각형 한변의 길이/2 )를 만족해야 합니다. (그렇지 않으면 작은 정사각형 안으로 점이 들어옵니다.)
위의 두 조건을 모두 만족하는 x좌표들이 존재한다면, 아래의 네 가지 경우 중 적어도 하나는 성립함을 알 수 있습니다. 위의 두 조건에서 생기는 영역들의 경계선들이기 때문입니다.
1. 중심 x좌표 = max_x-big_square/2 일 경우, N개의 점 모두 포함 가능.
2. 중심 x좌표 = min_x+big_square/2 일 경우, N개의 점 모두 포함 가능.
3. 중심 x좌표 = x + small_square/2일 경우, N개의 점 모두 포함 가능한 x가 존재. ( x = (min_y + 액자크기 < y < max_y - 액자크기) 를 만족하는 점의 x좌표 중 하나여야 함.)
4. 중심 x좌표 = x - small_square/2일 경우, N개의 점 모두 포함 가능한 x가 존재. ( x = (min_y + 액자크기 < y < max_y - 액자크기) 를 만족하는 점의 x좌표 중 하나여야 함.)
1, 2의 경우 체크는 O(N) 으로 간단하게 할 수 있습니다. 3, 4의 경우도, 가능한 x들을 정렬시켜 놓으면 O(N)으로 가능합니다.
*자세한 풀이는 코드를 참고해주시기 바랍니다.
코드 )
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 | // code by RiKang, weeklyps.com // 2012 ACM-ICPC Daejeon regional - L // BOJ 8899 Square Annulus #include <bits/stdc++.h> #define PII pair<int,int> using namespace::std; const int INF = 2140000000; int n,min_x,min_y,max_x,max_y; int big_square, small_square; PII xy[100005]; bool possible(int now){ small_square = big_square - 2*now; vector<int> v; for(int i=1; i<=n; i++) if (min_y+now < xy[i].second && xy[i].second < max_y-now) v.push_back(xy[i].first); if(v.size()==0) return true; int cand = max_x-big_square/2; for(int i=0; i<v.size(); i++){ if(abs(v[i]-cand)<small_square/2) break; if(i+1==v.size()) return true; } cand = min_x+big_square/2; for(int i=0; i<v.size(); i++){ if(abs(v[i]-cand)<small_square/2) break; if(i+1==v.size()) return true; } for(int i=0; i<v.size(); i++){ int cand = v[i]+small_square/2; if(cand >= max_x-big_square/2 && cand <= min_x+big_square/2){ if(i+1==v.size() || cand<=v[i+1]-small_square/2) return true; } cand = v[i]-small_square/2; if(cand >= max_x-big_square/2 && cand <= min_x+big_square/2){ if(i==0 || cand>=v[i-1]+small_square/2) return true; } } return false; } void solve(){ scanf("%d",&n); min_x = min_y = INF; max_x = max_y = -INF; for(int i=1; i<=n; i++){ scanf("%d %d",&xy[i].first,&xy[i].second); xy[i].first*=2, xy[i].second*=2; min_x = min(min_x,xy[i].first); max_x = max(max_x,xy[i].first); min_y = min(min_y,xy[i].second); max_y = max(max_y,xy[i].second); } if(max_x-min_x > max_y-min_y){ for(int i=1; i<=n; i++) swap(xy[i].first,xy[i].second); swap(min_x,min_y), swap(max_x,max_y); } big_square = max_y-min_y; sort(xy+1,xy+n+1); int l=-1, r=big_square/2; while(l+1<r){ int mid = (l+r)/2; if (possible(mid)) r=mid; else l=mid; } printf("%d.%d\n",r/2,r%2*5); } int main(){ int t; scanf("%d",&t); while(t--){ solve(); } return 0; } | cs |
'문제 풀이' 카테고리의 다른 글
[BOJ 8897] Slicing Tree (0) | 2018.01.11 |
---|---|
[BOJ 8898] 스포츠 전문 채널 GSK (0) | 2018.01.11 |
[BOJ 8890] Critical 3-Path (0) | 2018.01.11 |
[BOJ 8889] 등고선 지도 (0) | 2018.01.11 |
[BOJ 8893] Pandora (0) | 2018.01.11 |