现在的位置: 首页 > 综合 > 正文

uva10167 生日蛋糕 (枚举)

2018年12月19日 ⁄ 综合 ⁄ 共 543字 ⁄ 字号 评论关闭

题目大意:

一个圆饼,上面有2N个樱桃,切一刀,使两块上面都有相等的樱桃。

分析:

由于圆饼半径只有100,所以枚举A,B,-100到100.对于每一种A,B,看看直线两边点数是不是相同,注意题目中很多点不在饼上面。

code:

#include <stdio.h>

struct node
{
    int x, y;
}point[105];
void solve(int n)
{
    int A, B, v, l, r, i;
    for(A=-100; A <=100; A++)
    for(B=-100; B <=100; B++)
    {
        l = r = 0;
        for(i=0; i<n; i++)
        {
            v = A*point[i].x + B*point[i].y;
            if(v>0) l++;
            else if(v<0) r++;
            else break;
            if(l==r&&r==n/2)
            {
                printf("%d %d\n",A,B);
                return ;
            }
        }
    }
}
int main()
{
    int x, y, i, t, n;
    while(scanf("%d",&t),t)
    {
        n = 0;
        t <<=1;
        while(t--)
        {
            scanf("%d%d",&x,&y);
            if(x>=-100&&x<=100&&y>=-100&&y<=100)
            {
                point[n].x = x;
                point[n++].y = y;
            }
        }
        solve(n);
    }
    return 0;
}

抱歉!评论已关闭.