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;
}
上一篇: Fruit