티스토리 뷰

문제 풀이

[BOJ 8899] Square Annulus

RiKang 2018. 1. 11. 18:21

 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()==0return 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 8899] Square Annulus  (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