欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Birthday Cake Kattis - birthdaycake (几何)

程序员文章站 2022-04-01 20:39:12
...

题目 

https://cn.vjudge.net/problem/Kattis-birthdaycake

思路

给你一个圆,和n个点,m个直线,问能否把圆分成n块并每个块都有一个点

思路

暴力判断 1 判断能否分成n块 直线每有个交点就可以把一块分为两块,题目保证和圆相交就把圆分成 1 + m块,只看暴力两两求交点是否在园内

2 判断是否没块只有一个点,对于每个直线,把点两两带入,求是否被隔开

代码

 

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i<= (b);i++)
using namespace std;
typedef long long ll;
int mp[55][55];
struct node
{
    int x,y;
}p[55];
struct nodee
{
    int a,b,c;
}qw[55];
double r;
int ok(int a,int b,int c,int d,int e,int f)
{
    if(a*e == b*d) return 0;
    double x = ((double)(b*f) - (double)(c*e)) / ((double)(a*e) - (double)(b*d));
    double y = ((double)(a*f) - (double)(c*d)) / ((double)(b*d) - (double)(a*e));
    if(x*x + y*y <= (double)(r*r)) return 1;
    else return 0;
}
int main()
{
    int n,m;
    scanf("%d%d%lf",&n,&m,&r);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
    }
    memset(mp,0,sizeof(mp));
    for(int k = 1;k <= m;k++)
    {
        scanf("%d%d%d",&qw[k].a,&qw[k].b,&qw[k].c);
        int f = 0;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                if(j==i) continue;
                int x1 = p[i].x * qw[k].a + p[i].y * qw[k].b + qw[k].c;
                int x2 = p[j].x * qw[k].a + p[j].y * qw[k].b + qw[k].c;
                if(x1 * x2 <= 0) {mp[i][j] = mp[j][i] = 1;}
            }
        }
    }
    int qwe = m+1;
    for(int i = 1;i <= m;i++)
    {
        for(int j = i+1;j <= m;j++)
        {
            if(ok(qw[i].a,qw[i].b,qw[i].c,qw[j].a,qw[j].b,qw[j].c)) qwe++;
        }
    }
    if(qwe != n) printf("no\n");
    else
    {
        for(int i =1 ;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                if(i==j) continue;
                if(mp[i][j] == 0)
                {
                    printf("no\n");
                    return 0;
                }
            }
        }
        printf("yes\n");
    }
    return 0;
}