Background
Lucy and Lily are twins. Today is their birthday. Mother buys a birthday cake for them.Now we put the cake onto a Descartes coordinate. Its center is at (0,0), and the cake's length of radius is 100.
There are 2N (N is a integer, 1<=N<=50) cherries on the cake. Mother wants to cut the cake into two halves with a knife (of course a beeline). The twins would like to be treated fairly, that means, the shape of
the two halves must be the same (that means the beeline must go through the center of the cake) , and each half must have N cherrie(s). Can you help her?
Note: the coordinate of a cherry (x , y) are two integers. You must give the line as form two integers A,B(stands for Ax+By=0), each number in the range [-500,500]. Cherries are not allowed lying on the beeline.
For each dataset there is at least one solution.
Input
The input file contains several scenarios. Each of them consists of 2 parts: The first part consists of a line with a number N, the second part consists of 2N lines, each line has two number, meaning (x,y) .There
is only one space between two border numbers. The input file is ended with N=0.
Output
For each scenario, print a line containing two numbers A and B. There should be a space between them. If there are many solutions, you can only print one of them.
Sample Input
2
-20 20
-30 20
-10 -50
10 -5
0
Sample Output
0 1
因为半径较小,A,B是整数,因此可以直接枚举暴力搜索
#include<iostream>
using namespace std;
struct Node
{
int x,y;
}node[120];
int num;
bool line(int a,int b)
{
int r=0,t=0;
for(int i=0;i<num;i++)
{
if(node[i].x*a+node[i].y*b<0) r++;
else if(node[i].x*a+node[i].y*b>0) t++;
else break;
}
if(t==r&&r==num/2) return true;
else return false;
}
int main()
{
int n;
while(cin>>n&&n)
{
int i,j;
num=0;
for(i=0;i<2*n;i++)
{
int x1,y1;
cin>>x1>>y1;
if(x1*x1+y1*y1<=10000)
{
node[num].x=x1;
node[num].y=y1;
num++;
}
}
//cout<<num<<endl;
int tag=0;
for(i=-100;i<=100;i++)
{
for(j=-100;j<=100;j++)
{
if(line(i,j))
{
cout<<i<<" "<<j<<endl;
tag=1;
break;
}
}
if(tag) break;
}
}
return 0;
}
分享到:
相关推荐
很好的一款代码工具类,超级又使用
:birthday_cake:弃权日 现在,您有机会与工作中的同事一起纪念重要的弃用日标记。毕竟,我们必须庆祝自己的成就。 正在安装 使用composer进行安装,或将每个文件从github ui复制粘贴到您的磁盘上。 $ composer ...
生日庆祝birthday
happy_birthday
Birthday Calendar Get a birthday calendar for all your social networks right inside Google Calendar. Supports Facebook, LinkedIn, Xing, Skype, DavDroid and all other apps which sync contacts with ...
生男生女图,很准的。 新LOGO中,突出了”程序员”的中文名称,英文名称则更好地融入到杂志整体封面的设计中。在体现本土化的同时,又特别关注国际最新技术发展趋势。新更换的LOGO,将在即将上市的第四期杂志上正式...
Unit 6 Happy birthday! Part B 教案
Unit 6 Happy birthday! Part A 教案
三年级英语上册Unit6Happybirthday听力练习.doc
生日贺卡| 西德丹(Siddhant Sharma) :birthday_cake: 响应式生日贺卡-用Jquery和CSS制成(也有许多复活节彩蛋:-)
HappyBirthday!教学课件(Period5).ppt
人教版小学英语三年级上册unit6Happybirthday1PPT课件.pptx
Unit 6 Happy birthday! Part A 教案 3
Birthday.rar,太多无法一一验证是否可用,程序如果跑不起来需要自调,部分代码功能进行参考学习。
happy birthday to You英文生日祝福语.doc
中班英语教案《Happy birthday》润新教育.txt
人教版小学英语三年级上册unit6Happybirthday1PPT教案.pptx