제출 #218675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218675		Ruxandra985	Park (BOI16_park)	C++14	100 / 100	2224 ms	2296 KiB

park

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
deque <int> dq;
struct idk{
    int x , y , r;
} c[DIMN];
int val[5][5];
int dist[DIMN];
int n , w , h;
double distt (idk x , idk y){
    return sqrt ( 1LL * (x.x - y.x) * (x.x - y.x) + 1LL * (x.y - y.y) * (x.y - y.y) );
}
void solve (int nod , int raza){
    int i;
    memset (dist , 0 , sizeof(dist));
    dq.push_back(nod);
    dist[nod] = 1;
    while (!dq.empty()){
        nod = dq.front();
        dq.pop_front();

        for (i = 1 ; i <= n ; i++){
            if (dist[i])
                continue;
            if (nod <= n && distt(c[nod] , c[i]) < c[i].r + c[nod].r + 2 * raza){
                dist[i] = 1;
                dq.push_back(i);
            }
            else if (nod == n + 1 && c[i].y < c[i].r + 2 * raza) {
                dist[i] = 1;
                dq.push_back(i);
            }
            else if (nod == n + 2 && (w - c[i].x) < c[i].r + 2 * raza){
                dist[i] = 1;
                dq.push_back(i);
            }
            else if (nod == n + 3 && (h - c[i].y) < c[i].r + 2 * raza){
                dist[i] = 1;
                dq.push_back(i);
            }
            else if (nod == n + 4 && c[i].x < c[i].r + 2 * raza){
                dist[i] = 1;
                dq.push_back(i);
            }

        }

        if (nod <= n){
            i = nod;
            if (c[i].y < c[i].r + 2 * raza) {
                dist[n + 1] = 1;
            }
            if ((w - c[i].x) < c[i].r + 2 * raza){
                dist[n + 2] = 1;
            }
            if ((h - c[i].y) < c[i].r + 2 * raza){
                dist[n + 3] = 1;
            }
            if (c[i].x < c[i].r + 2 * raza){
                dist[n + 4] = 1;
            }


        }


    }

}


int connect (int i , int j , int raza){

    /// cu raza, liniile i si j se conecteaza?
    //if (i == 1 && j == 2)
      //  printf ("a");
    solve(n + i , raza);

    return dist[n + j];

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , m , j , st , dr , mid , en , r;
    fscanf (fin,"%d%d%d%d",&n,&m,&w,&h);
    /// w e pe ox , h e pe oy
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d%d%d",&c[i].x,&c[i].y,&c[i].r);
    }

    /// la ce raza incep sa fie conectate laturile intre ele??

    for (i = 1 ; i < 4 ; i++){
        for (j = i + 1 ; j <= 4 ; j++){
            st = 0;
            dr = 1000000000;
            while (st <= dr){
                mid = (st + dr)/2;
                if (connect (i , j , mid))
                    dr = mid - 1;
                else st = mid + 1;
            }

            val[i][j] = st; /// st e prima raza asa incat laturile i si j sunt conectate
        }
    }


    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%d%d",&r,&en);

        if (en == 1){

            fprintf (fout,"1");

            if (val[1][4] <= r){
                fprintf (fout,"\n");
                continue;
            }

            if (min(val[1][2] , val[1][3]) > r)
                fprintf (fout,"2");
            if (min(val[2][4] , min(val[1][3] , val[2][3])) > r)
                fprintf (fout,"3");
            if (min(val[2][4] , val[3][4]) > r)
                fprintf (fout,"4");


        }
        else if (en == 2){

            if (val[1][2] <= r){
                fprintf (fout,"2\n");
                continue;
            }

            if (min(val[1][4] , val[1][3]) > r)
                fprintf (fout,"1");

            fprintf (fout,"2");

            if (min(val[2][4] , val[2][3]) > r)
                fprintf (fout,"3");
            if (min(val[1][3] , min(val[2][4] , val[3][4])) > r)
                fprintf (fout,"4");

        }
        else if (en == 3){

            if (val[2][3] <= r){
                fprintf (fout,"3\n");
                continue;
            }

            if (min(val[2][4] , min(val[1][4] , val[1][3])) > r)
                fprintf (fout,"1");

            if (min(val[1][2] , val[2][4]) > r)
                fprintf (fout,"2");

            fprintf (fout,"3");

            if (min(val[1][3] , val[3][4]) > r)
                fprintf (fout,"4");

        }
        else if (en == 4){

            if (val[3][4] <= r){
                fprintf (fout,"4\n");
                continue;
            }

            if (min(val[1][4] , val[2][4]) > r)
                fprintf (fout,"1");

            if (min(val[2][4] , min(val[1][2] , val[1][3])) > r)
                fprintf (fout,"2");

            if (min(val[1][3] , val[2][3]) > r)
                fprintf (fout,"3");

            fprintf (fout,"4");

        }

        fprintf (fout,"\n");

    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'int main()':
park.cpp:88:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d%d",&n,&m,&w,&h);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:91:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d",&c[i].x,&c[i].y,&c[i].r);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:113:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&r,&en);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~

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