Problem G. Birthday Cake |
Problem's Link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=13&problem=1108&mosmsg=Submission+received+with+ID+14413715
Mean:
http://luckycat.kshs.kh.edu.tw/homework/q10167.htm
analyse:
由于A,B的范围在-500~500之间,所以直接枚举就可以了。
Time complexity: O(n*n*m)
Source code:
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-10-24-20.52
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
struct node
{
int x,y;
};
node p[110];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);
// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout);
int n,i,j,k,x,y;
while(cin>>n,n)
{
n<<=1;
for(int i=0;i<n;++i)
{
cin>>x>>y;
p[i].x=x,p[i].y=y;
}
int cnt;
bool f=0;
for(i=-500;i<=500;++i)
{
for(j=-500;j<=500;++j)
{
cnt=0;
for(k=0;k<n;++k)
{
if(p[k].x*i+p[k].y*j>0) cnt++;
if(p[k].x*i+p[k].y*j==0) break;
}
if(cnt==n>>1&&k==n)
{
cout<<i<<" "<<j<<endl;
f=1;
break;
}
}
if(f) break;
}
}
return 0;
}