| ? Problem G. Birthday Cake ? |
?
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
題解：暴力枚舉+線性規(guī)劃。A、B都是整數(shù)且范圍為[-500,500]，1<=N<=50，所以暴力枚舉即可。統(tǒng)計一下直線一側(cè)點的數(shù)目是否為N。注意有點在直線上的情況是不合法的。
代碼：
1
#include<stdio.h>
2
#include<
string
.h>
3
#include<stdbool.h>
4
5
int
i,j,n,m,sum,
6
a[
110
],b[
110
];
7
8
int
9
init()
10
{
11
int
i;
12
m=
2
*
n;
13
for
(i=
1
;i<=m;i++
)
14
scanf(
"
%d%d
"
,&a[i],&
b[i]);
15
16
return
0
;
17
}
18
19
int
20
main()
21
{
22
int
i,j,k,f;
23
while
(
true
)
24
{
25
scanf(
"
%d
"
,&
n);
26
if
(n==
0
)
break
;
27
init();
28
f=
0
;
29
for
(i=-
500
;i<=
500
;i++
)
30
{
31
for
(j=-
500
;j<=
500
;j++
)
32
{
33
sum=
0
;
34
for
(k=
1
;k<=m;k++
)
35
{
36
if
((i*a[k]+j*b[k])<
0
) sum++
;
37
if
((i*a[k]+j*b[k])==
0
)
break
;
38
}
39
if
(sum==
n)
40
{
41
f=
1
;
42
printf(
"
%d %d\n
"
,i,j);
43
break
;
44
}
45
}
46
if
(f==
1
)
break
;
47
}
48
}
49
50
return
0
;
51
}
52
?
?
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
