사용한 알고리즘
알고리즘 설명
- 위에서 주어지는 좌표로써 해석하는 것이 아니라 사각형의 중심으로 부터 이뤄지는 각도로써 문제를 해석하자.
- 두 점 <a,b>에 대해서 <c,d>가 교차할 조건은 아래와 같다.
- 전제:
a의 각도 < b의각도, c의 각도 < d의 각도 라고하면 a의 각도 < c의 각도 < b의 각도 < d의 각도를 만족해야한다.- 입력되는 (a,b)의 a값을 편의상 반 시계 방향을 기준으로 값을 치환하였다.
convert함수 참고 - 이후 두 선의 pair에 대한 판단이 이루어 지는데 이는
check함수에서 확인할 수 있다. - 여기서 cw(a,b)를 이용하여 두 점에 대해서 누가 더 작은 각도를 가지는지를 판단한다. (a 의 각도 < b의 각도)
- check에서 두 좌표 (1,2)와 (3,4)의 각도 관계가 (1,3,2,4)와 같이 엉켜있는 경우에 교차하는 조건이다.
- 먼저 cw13(1,3)과 cw14(1,4)의 cw 값에 따라 순서가 정해진다.
- cw13,cw14 = (0, 0) » (1,3,4) 순서
- cw13,cw14 = (0, 1) » (4,1,3) 순서
- cw13,cw14 = (1, 0) » (3,1,4) 순서
- cw13,cw14 = (1, 1) » (3,4,1) 순서
- 위와 같이 좌표 2에 대해서도 (2,3)과 (2,4)를 진행한뒤에 교차하는 조건을 조건으로 주면 된다. 조건은 아래와 같다.
- 조건:
(c13^c23)^(c14^c24)
풀이
// baekjoon 2650 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=51;
typedef pair<int,int> P;
typedef pair<pair<int,int>, pair<int,int> > PP;
int N;
PP point[MAX_N];
bool cw(P a, P b) {
if (a.first < b.first) return false;
if (a.first > b.first) return true;
if (a.first < 3) return a.second > b.second;
return a.second < b.second;
}
bool check(int a, int b) {
P p1 = point[a].first;
P p2 = point[a].second;
P p3 = point[b].first;
P p4 = point[b].second;
bool c13 = cw(p1, p3);
bool c23 = cw(p2, p3);
bool c14 = cw(p1, p4);
bool c24 = cw(p2, p4);
return (c13^c23)^(c14^c24);
}
int convert(int a) {
if (a == 3) return 1;
if (a == 2) return 2;
if (a == 1) return 4;
return 3;
}
int main() {
scanf("%d", &N);
N /= 2;
for (int i=0; i<N; i++) {
int a1, b1, a2, b2;
scanf("%d%d", &a1, &b1);
a1 = convert(a1);
scanf("%d%d", &a2, &b2);
a2 = convert(a2);
point[i] = make_pair(make_pair(a1,b1),make_pair(a2,b2));
}
int ret=0, ans=0;
for (int i=0; i<N; i++) {
int tmp = 0;
for (int j=0; j<N; j++) {
if (i == j) continue;
if (check(i, j)) {
tmp++;
}
}
ret += tmp;
ans = max(ans, tmp);
}
printf("%d\n%d\n", ret/2, ans);
return 0;
}
