Submission #347478

#	Time	Username	Problem	Language	Result	Execution time	Memory
347478		blue	Park (BOI16_park)	C++11	0 / 100	2580 ms	16108 KiB

park

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int sq(int a)
{
    return a*a;
}

int main()
{
    int n, m;
    cin >> n >> m;

    int w, h;
    cin >> w >> h;

    int x[n], y[n], r[n];
    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
    }

    //n = bottom edge, n+1 = right edge, n+2 = top edge, n+3 = left edge

    int maxGap[n+4][n+4];

    for(int i = 0; i < n; i++)
    {
        maxGap[i][n] = maxGap[n][i] = y[i] - r[i];
        maxGap[i][n+1] = maxGap[n+1][i] = w - (x[i] + r[i]);
        maxGap[i][n+2] = maxGap[n+2][i] = h - (y[i] + r[i]);
        maxGap[i][n+3] = maxGap[n+3][i] = x[i] - r[i];
    }

    for(int i = n; i < n+4; i++)
        for(int j = i+1; j < n+4; j++)
            maxGap[i][j] = maxGap[j][i] = 1e9;

    for(int i = 0; i < n; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            maxGap[i][j] = maxGap[j][i] = int(floor(sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j])))) - r[i] - r[j];
        }
    }







    for(int k = 0; k < n+4; k++)
    {
        for(int i = 0; i < n+4; i++)
        {
            if(i == k) continue;
            for(int j = 0; j < n+4; j++)
            {
                if(j == i || j == k) continue;

                maxGap[i][j] = min(maxGap[i][j], max(maxGap[i][k], maxGap[k][j]) );
            }
        }
    }


    // for(int i = 0; i < n+4; i++)
    // {
    //     for(int j = 0; j < n+4; j++)
    //     {
    //         if(i == j) cout << "* ";
    //         else cout << maxGap[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    int cornerGap[5][5];
    for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) cornerGap[i][j] = 1e9;

    vector<int> A, B;
    for(int i = 1; i <= 4; i++)
    {
        for(int j = i; j <= 4; j++)
        {
            cornerGap[i][j] = cornerGap[j][i] = 1e9;
            A.clear();
            B.clear();

            for(int k = 0; k < 4; k++)
            {
                if(i-1 <= k && k < j-1) A.push_back(n+k);
                else B.push_back(n+k);
            }

            for(int a:A) for(int b:B)
                cornerGap[i][j] = cornerGap[j][i] = min(cornerGap[i][j], maxGap[a][b]);
        }
    }

    // for(int i = 1; i <= 4; i++)
    // {
    //     for(int j = 1; j <= 4; j++) cout << cornerGap[i][j] << ' ';
    //     cout << '\n';
    // }



    int R, E;
    for(int i = 0; i < m; i++)
    {
        cin >> R >> E;
        for(int j = 1; j <= 4; j++)
        {
            if(cornerGap[E][j] >= 2*R) cout << j;
        }
        cout << '\n';
    }
}

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