제출 #987804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987804		alexdd	Park (BOI16_park)	C++17	100 / 100	505 ms	1976 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 2e9;
int n,m,h,w;
pair<int,int> t[2005];
int tr[2005];
bool visited[2005];
bool atinge(pair<int,int> p, int r, int margine)
{
    if(margine==1)
    {
        return (h-p.second)<r;
    }
    else if(margine==2)
    {
        return (w-p.first)<r;
    }
    else if(margine==3)
    {
        return p.second<r;
    }
    else
    {
        return p.first<r;
    }
}
int calc_dist(pair<int,int> x, pair<int,int> y)
{
    return (x.first-y.first)*(x.first-y.first) + (x.second-y.second)*(x.second-y.second);
}
void dfs(int x, int r)
{
    visited[x]=1;
    for(int i=1;i<=n;i++)
        if(!visited[i] && calc_dist(t[x],t[i]) < (tr[x]+tr[i]+2*r)*(tr[x]+tr[i]+2*r))
            dfs(i,r);
}
bool verif(int from, int to, int r)
{
    for(int i=1;i<=n;i++)
        visited[i]=0;
    for(int i=1;i<=n;i++)
        if(!visited[i] && atinge(t[i],2*r+tr[i],from))
            dfs(i,r);
    for(int i=1;i<=n;i++)
        if(visited[i] && atinge(t[i],2*r+tr[i],to))
            return 1;
    return 0;
}
int lim[5][5],rez[5][5];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>w>>h;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i].first>>t[i].second>>tr[i];
    }
    for(int from=1;from<=4;from++)
    {
        for(int to=from+1;to<=4;to++)
        {
            if(verif(from,to,0))
            {
                lim[from][to]=-1;
                continue;
            }
            int st,dr,ans;
            st=0;
            dr=INF;
            ans=0;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(!verif(from,to,mij))
                {
                    ans=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            lim[from][to] = lim[to][from] = ans;
            //cout<<from<<" "<<to<<"   "<<lim[from][to]<<" lim\n";
        }
    }
    rez[1][2] = rez[2][1] = min({lim[1][3],lim[4][3],lim[2][3]});
    rez[1][3] = rez[3][1] = min({lim[3][4],lim[1][3],lim[1][2],lim[2][4]});
    rez[1][4] = rez[4][1] = min({lim[2][4],lim[4][1],lim[4][3]});
    rez[2][3] = rez[3][2] = min({lim[2][4],lim[3][2],lim[1][2]});
    rez[2][4] = rez[4][2] = min({lim[1][3],lim[2][4],lim[1][4],lim[2][3]});
    rez[3][4] = rez[4][3] = min({lim[1][3],lim[4][1],lim[1][2]});
    int qe,qr;
    while(m--)
    {
        cin>>qr>>qe;
        for(int i=1;i<=4;i++)
            if(i==qe || rez[qe][i]>=qr)
                cout<<i;
        cout<<"\n";
    }
    return 0;
}
/**
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

*/

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42