SCPC 2020 2차 예선 풀이

1. 실력 맞추기

기본적으로 최적의 방식는 각 그룹을 실력 순으로 나열한 뒤 매칭시키는 것이다.

이제 $A$ 그룹의 사람 한 명의 실력을 바꾼다고 가정하자. 이때, 새로운 실력이 $B$ 그룹 중 한 사람의 실력과 일치하는 경우만 고려해도 무방하다.

이제 $A_i$를 $B_j$로 바꾼다고 가정하자. 만약 $i=j$라면, 공정도의 합은 $\sum_{k=1, k \neq i}^{n} |A_k - B_k|$다. 

만약 $i < j$라면, 공정도의 합은 $\sum_{k=1}^{i-1} |A_k - B_k| + \sum_{k=i+1}^j |A_k - B_{k-1}| + \sum_{k=j+1}^n |A_k-B_k|$가 된다.

만약 $i > j$라면, 공정도의 합은 $\sum_{k=1}^{j-1} |A_k - B_k| + \sum_{k=j+1}^i |A_{k-1} - B_k| + \sum_{k=i+1}^n |A_k-B_k|$이다.

이제 각 $i, j$에 대하여 저 값들 중 최솟값을 구하면 된다. 그런데 식의 형태가 상당히 부분합 느낌이 강하게 난다.

$i=j$인 경우는 $|A_k - B_k|$에 대한 부분합을 전부 계산하는 방식으로 처리할 수 있다. 

$i < j$인 경우에는 $-|A_i-B_i| + \sum_{k=i+1}^j (|A_k - B_{k-1}| - |A_k - B_k|) $의 최솟값을 구하는 것과 같다.

이는 최대 연속 구간합을 계산하는 방식과 동일하게 계산할 수 있다. $i$를 고정하고 최적의 $j$를 쉽게 구할 수 있기 때문이다.

$i >j$인 경우에도 동일한 접근이 가능하며, 쉽게 계산하려면 $A$ 배열과 $B$ 배열을 swap 한 뒤 위 경우를 그대로 적용해도 된다.

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, ans, dfdf;
ll a[222222];
ll b[222222];
ll c[222222];
ll d[222222];
 
void work(void)
{
    ll i; d[n]=1e18;
    for(i=1 ; i<=n-1 ; i++) c[i]=c[i-1]+abs(a[i+1]-b[i])-abs(a[i+1]-b[i+1]);
    for(i=n-1 ; i>=1 ; i--) d[i]=min(d[i+1], c[i]);
    for(i=1 ; i<=n ; i++) ans=min(ans, dfdf+d[i]-c[i-1]-abs(a[i]-b[i]));
}
 
void solve(void)
{
    ll i, j, mx=0; cin>>n; ans=0;
    for(i=1 ; i<=n ; i++) cin>>a[i]; sort(a+1, a+n+1);
    for(i=1 ; i<=n ; i++) cin>>b[i]; sort(b+1, b+n+1);
    for(i=1 ; i<=n ; i++) ans+=abs(a[i]-b[i]); dfdf=ans;
    for(i=1 ; i<=n ; i++) mx=max(mx, abs(a[i]-b[i])); ans-=mx;
    work(); for(i=1 ; i<=n ; i++) swap(a[i], b[i]); work();
    cout<<ans; return;    
}
 
int main(void)
{
    fio; ll i, tc; cin>>tc;
    for(i=1 ; i<=tc ;  i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}

2. 고구마

$a_i + a_{i+1} + \cdots + a_j \le M$을 만족하면서, $a_i + a_{i+1} + \cdots + a_j$를 최대화하고 싶다.

부분합 배열 $ps_i = a_1 +a_2 + \cdots + a_i$를 만들면, 목표는 $ps_j - ps_{i-1}$을 조건 아래에서 최대화하는 것이다.

$j$를 고정하자. 그러면 목표는 $ps_{i-1} \ge ps_j - M$이면서 최소인 $ps_{i-1}$을 찾는 것이다.

이는 $ps$ 배열을 원소로 갖는 std::set을 이용하여 쉽게 찾을 수 있다. 1번보다 훨씬 쉬운 문제.

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll a[333333], ps[322222], n, M, ans;
set<ll> S; set<ll>::iterator it;
 
void solve(void)
{
    ll i; cin>>n>>M; S.clear(); ans=0;
    for(i=1 ; i<=n ; i++) cin>>a[i]; S.insert(0);
    for(i=1 ; i<=n ; i++)
    {
        ps[i]=ps[i-1]+a[i];
        it=S.lower_bound(ps[i]-M);
        if(it!=S.end()) ans=max(ans, ps[i]-(*it));
        S.insert(ps[i]);
    }
    cout<<ans; return;
}
 
int main(void)
{
    fio; ll i, tc; cin>>tc;
    for(i=1 ; i<=tc ;  i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}

3. 아르바이트

1차 4번 문제의 느낌이 나는 문제인 것 같다. 

우선 중요한 점은, 하루의 급여가 바뀐 경우 최대 $k$개의 구간의 총합이 변화한다는 점이다. 즉, 구간의 합이 변화하는 총 횟수는 최대 $Qk$번이다. 

$n-k+1$개의 구간의 총합을 관리하고 있는 multiset이 있다고 하자. 우리는 이 multiset의 중앙값을 계속 구해야 한다.

총합 자체를 관리하는 것은 $\mathcal{O}(Qk + n)$에 쉽게 할 수 있으므로, 우리의 궁극적인 문제는 다음과 같다.

• 집합에 속한 원소 삭제
• 집합에 원소 하나 추가
• 집합의 중앙값 계산

다양한 접근이 가능하다. 첫 번째 접근은 세그먼트 트리를 이용한다.

가능한 구간의 합 $\mathcal{O}(Qk+n)$개를 전부 전처리 한 후 좌표압축하자. 

각 원소의 등장 횟수를 관리하는 합 세그먼트 트리를 관리하면, 이분탐색으로 답을 구할 수 있다.

세그먼트 트리를 구현할 경우 트리를 따라 내려가는 방식으로 이분탐색을 없앨 수 있다.

나는 중앙값을 계산하는 횟수가 $Q$로 적으므로, 세그먼트 트리 대신 펜윅을 사용하는 방식을 택했다.

그런데 이 방식을 구현했는데 TLE가 발생했다. 최적화를 했는데도 TLE여서 접근을 바꾸기로 했다.

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct Fenwick
{
    int tree[955555], C=450000;
    void init(void) { memset(tree, 0, sizeof(tree)); }
    void update(int x, int v) { while(x<=C) { tree[x]+=v; x+=(x&-x); } }
    int query(int x) { int ret=0; while(x) { ret+=tree[x]; x-=(x&-x); } return ret; }
    int rquery(int l, int r) { return query(r)-query(l-1); }
} T; 
 
int n, k, q;
int init[222222], ch[222222], ps[222222], res[222222];
int whi[222222], v[222222];
vector<int> POS;
 
int get_median(void)
{
    int lef, rig, mid, best;
    lef=1; rig=POS.size();
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(T.query(mid)>=(n-k+3)/2) best=mid, rig=mid-1;
        else lef=mid+1;
    }
    return POS[best-1];
}
 
void UPD(int vv, int t)
{
    int loc=lower_bound(POS.begin(), POS.end(), vv)-POS.begin()+1;
    T.update(loc, t); return;
}
 
void solve(void)
{
    int i, j, c=0, tt=0; cin>>n>>k>>q; 
    tt=n-k+1; POS.clear();
    for(i=1 ; i<=n ; i++) cin>>init[i];
    for(i=1 ; i<=q ; i++) cin>>whi[i]>>v[i]; 
    for(i=1 ; i<=q ; i++) tt+=min(whi[i], n-k+1)-max(1, whi[i]-k+1)+1;
    POS.resize(tt); T.C=tt+5;
    for(i=1 ; i<=n ; i++) ch[i]=init[i];
    for(i=1 ; i<=n ; i++) ps[i]=ps[i-1]+init[i]; // ps[i] : i ~ i+k-1
    for(i=1 ; i<=n-k+1 ; i++) res[i]=ps[i+k-1]-ps[i-1];
    for(i=1 ; i<=n-k+1 ; i++) POS[c++]=res[i];
    for(i=1 ; i<=q ; i++)
    {
        for(j=max(1, whi[i]-k+1) ; j<=min(whi[i], n-k+1) ; j++) 
        {
            res[j]+=v[i]-ch[whi[i]];
            POS[c++]=res[j];
        }
        ch[whi[i]]=v[i];
    }
    sort(POS.begin(), POS.end());
    POS.erase(unique(POS.begin(), POS.end()), POS.end());
    for(i=1 ; i<=n ; i++) ch[i]=init[i];
    for(i=1 ; i<=n ; i++) ps[i]=ps[i-1]+init[i];
    for(i=1 ; i<=n-k+1 ; i++) res[i]=ps[i+k-1]-ps[i-1];
    for(i=1 ; i<=n-k+1 ; i++) UPD(res[i], 1); cout<<get_median()<<" ";
    for(i=1 ; i<=q ; i++)
    {
        for(j=max(1, whi[i]-k+1) ; j<=min(whi[i], n-k+1) ; j++) 
        {
            UPD(res[j], -1);
            res[j]+=v[i]-ch[whi[i]];
            UPD(res[j], 1);
        }
        ch[whi[i]]=v[i];
        cout<<get_median()<<" ";
    }
    for(i=0 ; i<=2*tt+20 ; i++) T.tree[i]=0;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc; T.init();
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}

두 번째 방식은 priority_queue를 이용한다. 

$n-k+1$개의 수들 중 작은 절반을 관리하는 PQ와 큰 절반을 관리하는 PQ를 생각하자.

이를 관리하는 것은 어렵지 않은데, 다음을 반복하면 된다.

• 원소 삭제시, 해당 원소를 포함하는 PQ에서 원소 삭제
• 원소 추가시, 중앙값과 비교하여 적합한 PQ에 원소 추가
• 중앙값 계산시, 큰 절반을 관리하는 PQ에서 최소 원소 찾기
• 마지막으로, 양쪽 PQ의 원소 개수가 원하는 반반이 되도록 밸런스 맞추기

이제 문제는 PQ에서 원소를 삭제해야 한다는 것이다. 그런데 삭제 가능한 PQ가 있다!

나는 친구에게 들었는데, 대충 top()을 호출할 때 삭제된 얘들을 다 날리는 방식이다. 자세한 것은 코드 참고.

이 방식은 연산 자체가 훨씬 간단해서 더욱 빠르다. 제출 10번 채웠으면 억울해 죽을 뻔 ㅋㅋ

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int inf=1e9;
struct iHeap 
{
    priority_queue<int> q, qr;
    void rset(void) { while(!q.empty()) q.pop(); while(!qr.empty()) qr.pop(); }
    inline int size(void) { return q.size()-qr.size(); }
    inline void rmv(int x) { qr.push(x); }
    inline int top()
    {
        while(q.size() && qr.size() && q.top() == qr.top()) { q.pop(); qr.pop(); }
        return q.size()?q.top():-inf;
    }
    inline void push(int x) { q.push(x); }
} A, B;
 
int n, k, q, asz, bsz;
int init[222222], ch[222222];
int ps[222222], res[222222];
int cv[222222];
int whi[222222], v[222222];
vector<int> POS;
 
void rmv(int x)
{
    if(x<=A.top()) { A.rmv(x); }
    else { B.rmv(-x); }
}
 
void ins(int x)
{
    if(x<=A.top()) { A.push(x); }
    else { B.push(-x);  } 
}
 
void housekeep(void)
{
    while(A.size()>asz)
    {
        ll t=A.top(); A.rmv(t);
        B.push(-t);
    }
    while(B.size()>bsz)
    {
        ll t=B.top(); B.rmv(t);
        A.push(-t);
    }
}
 
void solve(void)
{
    int i, j; cin>>n>>k>>q; A.rset(); B.rset();
    for(i=1 ; i<=n ; i++) cin>>init[i];
    for(i=1 ; i<=q ; i++) cin>>whi[i]>>v[i]; 
    for(i=1 ; i<=n ; i++) ch[i]=init[i];
    for(i=1 ; i<=n ; i++) ps[i]=ps[i-1]+init[i]; 
    for(i=1 ; i<=n-k+1 ; i++) { res[i]=ps[i+k-1]-ps[i-1]; cv[i]=res[i]; }
    sort(cv+1, cv+(n-k+1)+1);
    for(i=1 ; i<=(n-k+1)/2 ; i++) { A.push(cv[i]); }
    for(i=(n-k+1)/2+1 ; i<=(n-k+1) ; i++) { B.push(-cv[i]); }
    asz=(n-k+1)/2; bsz=(n-k+1)-asz;
    cout<<-B.top()<<" ";
    for(i=1 ; i<=q ; i++)
    {
        for(j=max(1, whi[i]-k+1) ; j<=min(whi[i], n-k+1) ; j++) 
        {
            rmv(res[j]);
            res[j]+=v[i]-ch[whi[i]];
            ins(res[j]);
        }
        ch[whi[i]]=v[i]; housekeep();
        cout<<-B.top()<<" ";
    }
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}

4. 안전운전

가로선은 총합에 고려하지 않는다는 것을 늦게 읽어서 뇌절한 문제다. 

특정 $x$좌표 $T$에서 뒤집기를 시전했다고 가정하자. 그러면 그 후 경로의 모든 가로 좌표 $x$는 $2T-x$로 변환된다.

주어진 경로와 도로를 구간으로 쪼개서, 각 구간에서 경로/도로들의 가로 좌표가 고정되도록 하자.

이제 뒤집기 이전과 이후, 답에 더해지는 값들을 생각해보자.

• 뒤집기 이전에는 기존 경로 그대로 간다. 여기서 더해지는 값은 미리 전처리 가능하다.
• 뒤집는 가로선에서 $T$는 해당 가로선의 양 끝점 사이의 좌표가 된다.
• 뒤집기 이후에는 가로 좌표 $x$가 $2T-x$로 변환된다. 이후 구간에서 기존 가로 좌표가 $x$고, 왼쪽/오른쪽 도로의 가로 좌표가 각각 $L, R$인 경우, $L \le 2T-x \le R$인 경우에만 구간의 세로 길이가 답에 더해진다. 이는 부등식은 $(L+x)/2 \le T \le (R+x)/2$과 같다.

이제 뒤집는 가로선의 위치를 고정하고 생각하자. 이 가로선의 위치를 위에서부터 아래로 순서대로 본다.

매우 커다란 가상의 세그먼트 트리를 하나 준비한다.

• 각 구간에 대해, 세그트리의 구간 $[(L+x)/2, (R+x)/2]$에 해당 구간의 세로 길이만큼의 값을 더한다.
• 가로선이 등장한 경우, 그 가로선의 범위를 $[x_l, x_r]$이라 하자. 이 구간에서 세그트리의 최댓값을 뽑는다.
• 그 가로선 아래에서 얻어지는 값은 미리 전처리하였으므로, 이를 더한다.
• 이렇게 해서 얻어지는 값이 답의 후보이다. 이를 위에서부터 아래로 내려가면서 반복한다.

물론, 커다란 가상의 세그먼트 트리는 단순히 좌표압축으로 단순 세그먼트 트리로 바꿀 수 있다.

이제 필요한 것은 구간에 값 추가 + 구간 최댓값을 지원하는 세그먼트 트리고, 이는 lazy propagation으로 가능하다.

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct SegmentTree
{
    int tree[3588888];
    int lazy[3588888];
    void init(void) { memset(tree, 0, sizeof(tree)); memset(lazy, 0, sizeof(lazy)); }
    void workdown(int index, int s, int e)
    {
        if(s!=e)
        {
            lazy[index<<1]+=lazy[index];
            tree[index<<1]+=lazy[index];
            lazy[index<<1|1]+=lazy[index];
            tree[index<<1|1]+=lazy[index];
        }
        lazy[index]=0;
    }
    void update(int index, int s, int e, int l, int r, int v)
    {
        if(l>e || r<s) return; 
        workdown(index,s,e); 
        if(l<=s && e<=r) 
        {
            lazy[index]+=v;
            tree[index]+=v;
            return;
        }
        int m=(s+e)>>1;
        update(index<<1,s,m,l,r,v); 
        update(index<<1|1,m+1,e,l,r,v); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]);
    }
    int eval(int index, int s, int e, int l, int r)
    {
        if(l>e || r<s) return -1e9;
        workdown(index, s, e);
        if(l<=s && e<=r) return tree[index];
        int m=(s+e)>>1;
        int ret=max(eval(index<<1,s,m,l,r), eval(index<<1|1,m+1,e,l,r)); 
        tree[index]=max(tree[index<<1], tree[index<<1|1]); 
        return ret; 
    }
} T;
 
int ans, cnt, L, R, M, fin;
int lidx, ridx, midx;
int cut[666666];
pair<int, int> LF[222222], RG[222222], MM[222222];
vector<int> XP, RES;
int secL[666666], secR[666666];
int secM[666666], secV[666666];
 
void UPD(int u, int v, int er)
{
    u=lower_bound(RES.begin(), RES.end(), u)-RES.begin()+1;
    v=lower_bound(RES.begin(), RES.end(), v)-RES.begin()+1;
    T.update(1, 1, RES.size(), u, v, er);
}
 
int QUERY(int u, int v)
{
    if(u>v) swap(u, v);
    u=lower_bound(RES.begin(), RES.end(), u)-RES.begin()+1;
    v=lower_bound(RES.begin(), RES.end(), v)-RES.begin()+1;
    return T.eval(1, 1, RES.size(), u, v);
}
 
void solve(void)
{
    fio; ll i, j, x, y, u, v; cin>>L>>R>>M;
    XP.clear(); RES.clear(); cnt=0; ans=0;
    for(i=1, x=0, y=0 ; i<=L ; i++)
    {
        cin>>u>>v; x+=u; LF[i]=make_pair(y, x);
        XP.push_back(y); y+=v; fin=y;
    }
    for(i=1, x=0, y=0 ; i<=R ; i++)
    {
        cin>>u>>v; x+=u; RG[i]=make_pair(y, x); 
        XP.push_back(y); y+=v; fin=y;
    }
    for(i=1, x=0, y=0 ; i<=M ; i++)
    {
        cin>>u>>v; x+=u; MM[i]=make_pair(y, x); 
        XP.push_back(y); y+=v; fin=y;
    }
    sort(XP.begin(), XP.end()); 
    XP.erase(unique(XP.begin(), XP.end()), XP.end()); XP.push_back(fin);
    for(i=0, lidx=1, ridx=1, midx=1 ; i<XP.size() ; i++)
    {
        if(XP[i]==fin) break;
        while(lidx<=L && LF[lidx].first<=XP[i]) lidx++; lidx--;
        while(ridx<=R && RG[ridx].first<=XP[i]) ridx++; ridx--;
        while(midx<=M && MM[midx].first<=XP[i]) midx++; midx--;
        ++cnt; secL[cnt]=LF[lidx].second; secR[cnt]=RG[ridx].second;
        secM[cnt]=MM[midx].second; secV[cnt]=XP[i+1]-XP[i];
        RES.push_back((secL[cnt]+secM[cnt])/2); RES.push_back((secR[cnt]+secM[cnt])/2);
    }
    for(i=1 ; i<=cnt-1 ; i++)
    {
        if(secM[i]!=secM[i+1]) 
        {
            RES.push_back(secM[i]);
            RES.push_back(secM[i+1]);
        }
    }
    sort(RES.begin(), RES.end());
    RES.erase(unique(RES.begin(), RES.end()), RES.end());
    for(i=1 ; i<=cnt ; i++)
    {
        cut[i]=cut[i-1];
        if(secL[i]<=secM[i] && secM[i]<=secR[i]) cut[i]+=secV[i];
    }
    ans=cut[cnt];
    for(i=cnt ; i>=2 ; i--)
    {
        UPD((secL[i]+secM[i])/2, (secR[i]+secM[i])/2, secV[i]);
        if(secM[i]!=secM[i-1]) ans=max(ans, cut[i-1]+QUERY(secM[i-1], secM[i]));
    }
    for(i=0 ; i<=4*RES.size() ; i++) T.tree[i]=T.lazy[i]=0;
    cout<<ans; return;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc; T.init();
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}

5. 삼각형의 거리

볼록다각형의 경우 작년 ICPC 기출문제다. 그대로 제출하면 47점이다.

이제 본격적으로 문제를 해결해보자. 답에 대하여 이분탐색을 하자. 답이 $m$ 이하가 될 수 있는지 판별하자.

정점을 반시계 순서대로 $v_1, v_2, \cdots, v_n$이라고 하자. 

각 $i<j$에 대하여 $P_{i, j}$를 $v_i, v_{i+1}, \cdots , v_j$로 이루어진 다각형이라고 하자.

단, $v_i v_j$가 문제에서 주어진 다각형 내부에 완전히 위치해야 한다.

이제 $DP[i][j]$를 $P_{i, j}$를 지름을 $m$ 이하로 삼각분할 할 때, [$v_iv_j$를 포함하는 삼각형에서 가장 먼 삼각형까지의 거리]로 가능한 것 중 최솟값에 $1$을 더한 값이라고 하자. 만약 조건을 만족하는 삼각분할이 불가능하면 $\infty$라 하자.

$DP[i][j]$를 계산하기 위해, 점화식을 설계하자. $k \in [i+1, j-1]$을 하나 잡고 $v_i v_k v_j$가 정당한 삼각형인지를 판별하자.

만약 정당하다면, $v_iv_jv_k$와 $P_{i, k}$의 삼각분할, $P_{k, j}$의 삼각분할로 구성된 $P_{i, j}$의 삼각분할을 생각할 수 있다.

이 경우 지름은 $DP[i][k] + DP[k][j]$가 되며, 이 값이 $m$ 초과인 경우 실패라고 볼 수 있다.

성공이라면, $DP[i][j]$로 가능한 값 중 하나는 $\text{max}(DP[i][k], DP[k][j]) + 1$이 된다. 이를 업데이트 하자.

이렇게 되면 고려해야 할 $DP$ 상태는 $\mathcal{O}(n^2)$, 전이 시간복잡도도 $\mathcal{O}(n^3)$이다.

이제 본격적으로 기하적 부분을 처리해야 한다. 고통스러웠다 :(

$v_i v_k v_j$가 정당한 삼각형인지 판별하는 것은 각 변이 주어진 다각형 안에 속하는지만 판별해도 된다.

이제 선분 $v_iv_j$가 주어진 다각형 안에 속하는지 판별하는 방법을 생각해보자.

우선 다각형의 선분들 중 $v_i v_j$와 만나는 것은 없어야 한다. (끝점 제외)

이 판별이 끝나면, $v_i v_j$는 전부 다각형 내부에 속하거나 전부 다각형 외부에 속한다.

그러니, $v_iv_j$의 중점을 잡고 다각형 내부에 속하는지 판별하면 끝난다!

Point in Polygon은 ray casting algorithm으로 하면 되며, 설명은 여기를 참고하자. 

중점을 계산해야 하는데 소수점 나오면 기분이 나쁘니 모든 좌표를 2배해서 계산을 편하게 하자.

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll inf=1e9;
 
struct point_2d // ll
{
    ll x, y;
    point_2d() {}
    point_2d(ll x, ll y): x(x), y(y) {}
    bool operator==(const point_2d &t) { return x==t.x && y==t.y; }
    point_2d& operator+=(const point_2d &t) { x+=t.x; y+=t.y; return *this; }
    point_2d& operator-=(const point_2d &t) { x-=t.x; y-=t.y; return *this; }
    point_2d& operator*=(const ll t) { x*=t; y*=t; return *this; }
    point_2d& operator/=(const ll t) { x/=t; y/=t; return *this; }
    point_2d operator+(const point_2d &t) const { return point_2d(*this)+=t; }
    point_2d operator-(const point_2d &t) const { return point_2d(*this)-=t; }
    point_2d operator*(const ll t) const { return point_2d(*this)*=t; }
    point_2d operator/(const ll t) const { return point_2d(*this)/=t; }
    ll cross(const point_2d &t) const { return x*t.y-y*t.x; }
    ll cross(const point_2d &a, const point_2d &b) const { return (a-(*this)).cross(b-(*this)); }
};
 
bool inter_1d(ll a, ll b, ll c, ll d) 
{
    if(a>b) swap(a, b);
    if(c>d) swap(c, d);
    return max(a,c)<=min(b,d);
}
 
int sgn(ll x)
{
    if(x>0) return 1;
    if(x==0) return 0;
    if(x<0) return -1;
}
 
bool check_inter(point_2d a, point_2d b, point_2d c, point_2d d)
{
    if(c.cross(a,d)==0 && c.cross(b,d)==0 && c.cross(a,b)==0) // a, b, c, d colinear
        return inter_1d(a.x,b.x,c.x,d.x) && inter_1d(a.y,b.y,c.y,d.y);
    return sgn(a.cross(b,c))!=sgn(a.cross(b,d)) && sgn(c.cross(d,a))!=sgn(c.cross(d,b));
}
 
int n;
point_2d pt[333];
int isok[311][311];
int dp[311][311];
 
bool chk(int x)
{
    int i, j, k, inf=1e9;
    for(i=1 ; i<=n-1 ; i++)
    {
        for(j=1 ; j<=n-i ; j++)
        {
            if(i==1) { dp[j][j+i]=0; continue; } 
            if(isok[j][j+i]==0) { dp[j][j+i]=inf; continue; }
            dp[j][j+i]=inf;
            for(k=j+1 ; k<=j+i-1 ; k++)
            {
                if(isok[j][k]==0 || isok[k][j+i]==0) continue;
                if(dp[j][k]+dp[k][j+i]>x) continue;
                dp[j][j+i]=min(dp[j][j+i], max(dp[j][k], dp[k][j+i])+1);
            }
        }
    }
    if(dp[1][n]<5000) return true; return false;
}
 
bool inConcave(point_2d X)
{
    int i, cnt=0;
    point_2d Y; Y.x=inf+1; Y.y=X.y+1;
    for(i=1 ; i<=n ; i++) if(pt[i]==X) return true;
    for(i=1 ; i<=n ; i++) 
        if(check_inter(pt[i], pt[i%n+1], X, Y)) cnt++;
    return cnt%2==1;
}
 
int chk(int u, int v)
{
    if(v==u+1 || (u==1 && v==n)) return 1;
    for(int i=1 ; i<=n ; i++)
    {
        if(i==u || i%n+1==u || i==v || i%n+1==v) continue;
        if(check_inter(pt[u], pt[v], pt[i], pt[i%n+1])) return 0;
    }
    point_2d TT; TT.x=(pt[u].x+pt[v].x)/2; TT.y=(pt[u].y+pt[v].y)/2;
    if(!inConcave(TT)) return 0; return 1;
}
 
void solve(void)
{
    int i, j, k; cin>>n;
    for(i=1 ; i<=n ; i++) cin>>pt[i].x>>pt[i].y;
    for(i=1 ; i<=n ; i++) pt[i]*=2;
    if(n==3) { cout<<0; return; }
    if(n==4) { cout<<1; return; }
    for(i=1 ; i<=n ; i++)
        for(j=i+1 ; j<=n ; j++)
            isok[i][j]=chk(i, j);
    int lef=0, rig=n, mid, best=n; 
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(chk(mid)) best=mid, rig=mid-1;
        else lef=mid+1;
    }
    cout<<best; return;
}
 
int main(void)
{
    fio; int i, tc; cin>>tc;
    for(i=1 ; i<=tc ; i++)
    {
        cout<<"Case #"<<i<<"\n";
        solve(); cout<<"\n";
    }
    return 0;
}