글 읽기 - 반례가 잘 안보입니다.

wnguscjf01 2년 전 0

시계방향으로 점들을 정렬한 후 convex hull 중에서 하나를 선택하여 그 점을 기준으로 시계방향으로 정렬하여 빨간점과 파란점의 비가 2:1이 되게 나누어 분할정복하였습니다. 반례를 잘 모르겠습니다.

문제조건을 만족하지 않는 답이 존재하지 않는 경우도 구체적으로 알려주시면 감사하겠습니다.

#include<bits/stdc++.h>
#define MAXN 1001
using namespace std;
struct data{
	int num, col;
	long long int x, y;
};
struct data d[3*MAXN], sortkey;
long long int cross(long long int v1x, long long int v1y, long long int v2x, long long int v2y){
	return v1x*v2y - v1y*v2x;
}
bool comparex(struct data &a, struct data &b){
	return a.x < b.x;
}
bool compsortkey(struct data &a, struct data &b){
	return cross(a.x-sortkey.x, a.y-sortkey.y, b.x-sortkey.x, b.y-sortkey.y) < 0;
}
int ans[MAXN][2], hull[3*MAXN], ht, n;
bool noans;
int f(int st, int end){
	//printf("%d %d\n",st,end);
	if(end-st<2) return 0;
	if(end-st==2){
		if(d[st].col == 2){
			ans[d[st].num][0] = d[st+1].num;
			ans[d[st].num][1] = d[st+2].num;
		}
		if(d[st+1].col == 2){
			ans[d[st+1].num][0] = d[st].num;
			ans[d[st+1].num][1] = d[st+2].num;
		}
		if(d[st+2].col == 2){
			ans[d[st+2].num][0] = d[st].num;
			ans[d[st+2].num][1] = d[st+1].num;
		}
		return 0;
	}
	sort(d+st,d+end+1,comparex);
	sortkey = d[st];
	sort(d+st+1,d+end+1,compsortkey);
	int i, j;
	ht = 0;
	hull[++ht] = st;
	hull[++ht] = st+1;
	for(i=st+2; i<=end; i++){
		hull[++ht] = i;
		while(cross(d[hull[ht]].x-d[hull[ht-1]].x, d[hull[ht]].y-d[hull[ht-1]].y, d[hull[ht-2]].x-d[hull[ht-1]].x, d[hull[ht-2]].y-d[hull[ht-1]].y) > 0){
			hull[ht-1] = hull[ht];
			ht--;
		}
	}
	while(cross(d[st].x-d[hull[ht]].x, d[st].y-d[hull[ht]].y, d[hull[ht-1]].x-d[hull[ht]].x, d[hull[ht-1]].y-d[hull[ht]].y) > 0){
		ht--;
	}
	int p, prev, cnt;
	struct data tmp, backup[3*MAXN];
	for(i=st; i<=end; i++) backup[i] = d[i];
	for(j=1; j<=ht; j++){
		tmp = d[st]; d[st] = d[hull[j]]; d[hull[j]] = tmp;
		sortkey = d[st];
		sort(d+st+1,d+end+1,compsortkey);
		if(d[st].col == 2){
			p=0; cnt=0;
			prev = st+1;
			for(i=st+1; i<=end; i++){
				p += d[i].col;
				if(p-d[i].col == 0 && p == -1){
					ans[d[st].num][cnt++] = d[i].num;
					f(prev,i-1);
					prev = i+1; p=0;
					if(cnt>=2){
						break;
					}
				}
			}
			if(cnt<2) continue;
			i++; p=0;
			for(; i<=end; i++){
				p += d[i].col;
				if(p==0){
					f(prev,i);
					prev = i+1;
				}
			}
			break;
		}
		else{
			p=-1; prev = st;
			for(i=st+1; i<=end; i++){
				p += d[i].col;
				if(p==0 && !(i==end && prev==st)){
					f(prev,i);
					prev = i+1;
				}
			}
			if(prev!=st) break;
		}
		for(i=st; i<=end; i++) d[i] = backup[i];
	}
	if(j>ht) noans=1;
	
	return 0;
}
int main()
{
	int i, j;
	cin >> n;
	for(i=1; i<=n; i++){
		long long int a, b;
		scanf("%lld%lld",&a,&b);
		d[i].x=a; d[i].y=b; d[i].num=i; d[i].col=2;
	}
	for(i=1; i<=2*n; i++){
		long long int a, b;
		scanf("%lld%lld",&a,&b);
		d[n+i].x=a; d[n+i].y=b; d[n+i].num=n+i; d[n+i].col=-1;
	}
	f(1,3*n);
	if(noans) printf("-1");
	else{
		for(i=1; i<=n; i++) printf("%d %d\n",ans[i][0]-n,ans[i][1]-n);
	}
	return 0;
}

wnguscjf01 2년 전 0

음? 그냥 모든 경우 다 연결이 되네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 잘 안보입니다.

wnguscjf01 2년 전 0

wnguscjf01 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말