這道題是直接暴力，需要注意的是cherry不能在直線上，因此需要兩個變量來分別統(tǒng)計在直線兩邊的個數(shù)；
還想到一種方法：把所有斜率排序，然后二分枚舉，復(fù)雜度為O(n+n*lgn+lgn)。
1
# include <stdio.h>
2
3
int
c[
105
][
2
];
4
5
int
main()
6
{
7
int
n, c1, c2, A, B, i, ans[
2
];
8
9
while
(
1
)
10
{
11
scanf(
"
%d
"
, &n);
12
if
(!n)
break
;
13
14
for
( i =
1
; i <=
2
*n; ++i)
15
scanf(
"
%d%d
"
, &c[i][
0
], &c[i][
1
]);
16
17
for
( A =
0
; A <=
500
; ++A)
18
for
( B = -
500
; B <=
500
; ++B)
19
{
20
c1 =
0
;
21
c2 =
0
;
22
for
( i =
1
; i <=
2
*n; ++i)
23
if
(c[i][
0
]*A+c[i][
1
]*B >
0
) ++c1;
24
else
if
(c[i][
0
]*A+c[i][
1
]*B <
0
) ++c2;
25
if
(c1 == n && c2 == n)
26
{
27
ans[
0
] = A;
28
ans[
1
] = B;
29
B =
501
;
30
A =
501
;
31
}
32
}
33
34
printf(
"
%d %d\n
"
, ans[
0
], ans[
1
]);
35
}
36
37
return
0
;
38
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
