백준 5180, 피자!

개요

문제 링크
골드 3, Geometry
포함하는 특정점의 개수가 같고 크기가 같도록 원을 나누는 최대 개수

---

접근

1. 요상한 애드혹 문제, 틀왜맞이 절로 나왔다.
2. 이분탐색이나, 스위핑, 별의 별 방법을 다 생각해봤지만 N수가 적어서 그냥 for문을 돌면서 다 체크해주면 통과한다.
3. 다 체크란 어떻게 하냐? n부터 2까지 조각을 쪼갤 건데, 시작을 0부터 2π/n까지 하고, 개수가 모두 같으면 조각수를 출력해주면 된다. 즉 4중 for문 돌려주면 된다.

---

Pseudo code

for (piece = n~2)
    angle_diff = 2pi/piece
    for (start = 0~angle_diff)
        for (i = 0~piece)
            piece_start = start + i * angle_diff
            piece_end = start + (i+1) * angle_diff

            count = 0
            for (j = 0~n)
                if (piece_start <= angle[i] < piece_end)
                    count++
        if (count가 모두 같으면)
            answer = piece

---

Source code

#include <iostream>
using namespace std;

using ld = double;
#define PI 3.1415926535

const int N = 210;
int n;
ld a[N], eps = 0.001;

int count(ld t1, ld t2) {
    int cnt = 0;
    if (2*PI < t2)
        t2 -= 2*PI;
    for (int i=0; i<n; i++) {
        if (t1 <= a[i] && a[i] < t2)
            cnt++;
        else if (t2 < t1)
            if (a[i] < t2 || t1 <= a[i])
                cnt++;
    }
    return cnt;
}

int counta(ld s, ld dt, int n) {
    int cnt = count(s,s+dt);
    for (int i=1; i<n; i++)
        if (count(s+i*dt, s+(i+1)*dt)!=cnt)
            return 0;
    return 1;
}

int valid(int n) {
    ld dt = 2*PI/n;
    for (ld s=0; s<dt; s+=eps)
        if (counta(s, dt, n))
            return 1;
    return 0;
}

int test() {
    ld r;
    cin >> n;
    for (int i=0; i<n; i++)
        cin >> a[i] >> r;
    for (int i=n; i>=2; i--)
        if (valid(i))
            return i;
    return 1;
}

int main() {
    int t;
    cin >> t;
    for (int i=1; i<=t; i++)
        cout << "Data Set " << i << ": " << test() << " slices\n\n";
}