数学题(直线分割)UVA 10167-Birthday Cake

超、凢脫俗 2022-05-15 22:54 151阅读 0赞

*  # 数学题(直线分割)UVA 10167-Birthday Cake #

--------------------

*  ## 题目链接：[10167 - Birthday Cake][] ##
 *  ## 思路： ##

**题目大意是给定N，有2N颗樱桃分布在圆心在原点的蛋糕上，求A，B，过原点切蛋糕，切割线为Ax+By=0，要求切割线不过任何一颗樱桃的坐标，并让樱桃平均分布在蛋糕的两半。**

**N is a integer, 1 ≤ N ≤ 50 ；two integers A, B (stands for Ax + By = 0) each number mustn’t in \[−500, 500\]**

数据量不是很大，而且可以将A或B某一个取值减枝成0-500（**半圆的切割线延长线是整个圆**），直接穷举

**a. Ax+By=0 樱桃落在切割线，不符合**

**b. Ax+By>0 樱桃落在切割线之上 num1++**

**c. Ax+By<0 樱桃落在切割线之下 num2++**

**如果num1=num2=N，符合要求**

*  ## 代码： ##

#include <iostream>
    using namespace std;
    struct Point{
        int x;
        int y;
    };
    
    Point num[200];
    int main()
    {
        int N;
        while(cin>>N&&N)
        {
            for(int i=0;i<2*N;i++)
                cin>>num[i].x>>num[i].y;
            int A,B;
            int Pass_1=0,Pass_2=0;
            for(B=0;B<=500;B++)   //y
            {
                int f2=0;
                for(A=-500;A<=500;A++)
                {
                    int f1=0;
                    for(int i=0;i<2*N;i++)
                    {
                        if(A*num[i].x+B*num[i].y==0)
                        {
                            f1=1;
                            break;
                        }
                        if(A*num[i].x+B*num[i].y>0)
                            Pass_1++;
                        if(A*num[i].x+B*num[i].y<0)
                            Pass_2++;
                    }
    
    
                    if(f1!=1&&Pass_1==N)
                    {
                        cout<<A<<" "<<B<<endl;
                        f2=1;
                        break;
                    }
                    else
                    {
                        Pass_1=0;
                        Pass_2=0;
                    }
                }
                if(f2==1)
                    break;
            }
        }
        return 0;
    }

[10167 - Birthday Cake]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1108