Birthdat Cake/하기웅

풀이 ¶

처음엔 뭔가 획기적인 방법이 없을까 생각을 많이하다가 그냥 노가다로 짜버렸다^^
그런데 뭐 단방에 Accepted가 되니 황당하다^^

ax+by=0 이라는 식이 있을때, 여기에 x,y를 대입해서 ax+by>0면 -a/b라는 기울기의 직선보다 위에 있는 점이라는 것이고
ax+by<0면 -a/b라는 기울기의 직선보다 아래에 있는 점이다.

이것을 이용해서 a, b를 for문을 통해 변화 시켜가면서 위에 있는 점과 아래에 있는 점이 개수가 똑같은 때의 기울기를 찾는 방식.

소스 ¶

~cpp
#include <iostream>
using namespace std;

struct Point {
	int x;
	int y;
};

int cherry, i, j, k, a, b;
Point ch[100];

Point getLine()
{
	Point temp;
	for(i=0; i<500; i++)
	{
		for(j=1; j<=500; j++)
		{
			a=0; b=0;
			for(k=0; k<2*cherry; k++)
			{
				if((i*ch[k].x+j*ch[k].y)>0)
					a++;
				else if((i*ch[k].x+j*ch[k].y)<0)
					b++;
			}

			if(a==cherry && b==cherry)
			{
				temp.x = i;
				temp.y = j;
				return temp;
			}
		}
		for(j=-1; j>=-500; j--)
		{
			a=0; b=0;
			for(k=0; k<2*cherry; k++)
			{
				if((i*ch[k].x+j*ch[k].y)>0)
					a++;
				else if((i*ch[k].x+j*ch[k].y)<0)
					b++;
			}

			if(a==cherry && b==cherry)
			{
				temp.x = i;
				temp.y = j;
				return temp;
			}
		}
	}
}

int main()
{
	while(cin>>cherry)
	{
		if(cherry==0)
			break;
		for(i=0; i<2*cherry; i++)
			cin >> ch[i].x >> ch[i].y;
		cout << getLine().x <<" " <<getLine().y<< endl;	
	}
	return 0;
}