[BOJ] 1004

less than 1 minute read

어린 왕자

1004번 https://www.acmicpc.net/problem/1004

분류

  • Silver 3
  • 기하학

해법

어떤 길로도 갈 수 있기 때문에 출발지와 도착지 중
하나만 속하는(XOR) 은하계의 수를 합하면 됩니다.

정답 코드

#include <iostream>
#include <cmath>
using namespace std;

struct Point
{
    int xpos;
    int ypos;
};


struct Bound
{
    Point cen;
    int radius;
};


bool InBound(Point p, Bound b)
{
    double distFromCen = sqrt( pow(p.xpos-b.cen.xpos, 2) + pow(p.ypos-b.cen.ypos, 2) );
    return (distFromCen <= b.radius);
}

int main(void)
{
    int T;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int n;
        Point startPoint;
        Point endPoint;
        int cnt = 0;

        cin >> startPoint.xpos >> startPoint.ypos;
        cin >> endPoint.xpos >> endPoint.ypos;
        cin >> n;
        Bound* boundaries = new Bound[n];
        for (int i = 0; i < n; i++)
        {
            cin >> boundaries[i].cen.xpos >> boundaries[i].cen.ypos >> boundaries[i].radius;
            // cnt + 1 if boundary contain only one
            cnt = (InBound(startPoint, boundaries[i]) != InBound(endPoint, boundaries[i])) ? cnt + 1 : cnt;
        }

        cout << cnt << endl;
        delete []boundaries;
    }  
    return 0;
}

Categories:

Updated:

Leave a comment