UVa 10167 - Birthday Cake

系统 2228 0

这道题是直接暴力,需要注意的是cherry不能在直线上,因此需要两个变量来分别统计在直线两边的个数;

还想到一种方法:把所有斜率排序,然后二分枚举,复杂度为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 }

UVa 10167 - Birthday Cake


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论