PS/Topcoder training

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)

YongHoonJJo 2018. 7. 16. 11:15

### 수학 ###


### SRM 443 Div2 Level 2 ###



<소스트리>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
using namespace std;
 
double dist(int x1, int y1, int x2, int y2)
{
    return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}
 
class CirclesCountry {
public:
    int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
        
        int ans=0;
        for(int i=0; i<X.size(); i++) {
            double d1 = dist(X[i], Y[i], x1, y1);
            double d2 = dist(X[i], Y[i], x2, y2);
            double r = (double)R[i]*R[i];
            if(d1 < r) ans++;
            if(d2 < r) ans++;
            if(d1 < r && d2 < r) ans -= 2;
        }
        return ans;
    }
};
cs


>>> 기본 아이디어는 시작 좌표와 목표 좌표가 둥근성에 포함되어 있으면 카운트.

>>> 예외처리 : 같은 성에 동시에 포함되어 있으면 카운트하면 안된다.