글 읽기 - 2244 민코프스키 합 질문

pichulia 9년 전 0

평범한 convex hull 문제인줄로만 알았는데..

1. 제가 짠 convex hull 코드에 문제가 있나요?

물론 atan2를 쓴다는게 좀 위험해보이긴한데.. 숫자 범위가 20000 이라서 괜찮을거라 생각했습니다.

2. 원문을 보니까 번역문이랑 완전 다른 문제던데 혹시 이와 관련해서

데이터에 이상이 생긴건 아닐까... 라느 위험한 추측(?!)도 해봅니다.ㅋㅋㅋ

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
int n, m;
pii a[1502];
pii b[1502];
pii c[1500002];
int cl;
pair<double, int> d[1500002];
int e[1500002];
int el;
int ccd(pii p, pii q, pii r)
{
    int xx = p.first*q.second + q.first * r.second + r.first*p.second;
    int yy = p.second*q.first + q.second * r.first + r.second*p.first;
 
    return xx-yy;
}
int main()
{
	int i, j;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
		scanf("%d %d",&a[i].first,&a[i].second);
	for(i=0;i<m;i++)
		scanf("%d %d",&b[i].first,&b[i].second);
	cl=0;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			c[cl].first = a[i].first+b[j].first;
			c[cl].second = a[i].second + b[j].second;
			cl++;
		}
	sort(c,c+cl);
	cl=unique(c,c+cl)-c;
	for(i=1;i<cl;i++)
	{
		d[i].first = atan2(c[i].second-c[0].second,c[i].first - c[0].first);
		d[i].second = i;
	}
	sort(d+1,d+cl);

	e[0] = 0;
	e[1] = d[1].second;
	el=2;
	d[cl].second = 0;
	for(i=2;i<=cl;i++)
	{
		if(el<2)
		{
			e[el++] = d[i].second;
		}
		else
		{
			j = ccd(c[e[el-2]], c[e[el-1]], c[d[i].second]);
			if(j<0)
			{
				el--;
				i--;
			}
			else if(j==0 && (
				abs(c[e[el-2]].first - c[e[el-1]].first) + abs(c[e[el-2]].second - c[e[el-1]].second)
                < abs(c[e[el-2]].first - c[d[i].second].first) + abs(c[e[el-2]].second - c[d[i].second].second)
				))
			{
				el--;
				i--;
			}
			else if(j==0 && (
				abs(c[e[el-2]].first - c[e[el-1]].first) + abs(c[e[el-2]].second - c[e[el-1]].second)
                > abs(c[e[el-2]].first - c[d[i].second].first) + abs(c[e[el-2]].second - c[d[i].second].second)
				))
			{
				continue;
			}
			else
			{
				e[el++] = d[i].second;
			}
		}
	}
	printf("%d\n",el-1);
	for(i=0;i<el-1;i++)
	{
		printf("%d %d\n",c[e[i]].first, c[e[i]].second);
	}

}

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

문제

문제

출처

ICPC

2244 민코프스키 합 질문

pichulia 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말