[AHOI2016初中组]迷宫
2024-10-13 15:23:37
题目描述
小雪和小可可被困在了一个无限大的迷宫中。
已经知道这个迷宫有 N 堵环状的墙,如果把整个迷宫看作是一个二维平面,那么每一堵墙都是平面上一个圆。任意两个圆不相交,不重合,也不会相切, 但有可能相互包含。小雪和小可可分别被困在了 2 个不同的位置,且保证他们的位置与这些圆不重合。
他们只有破坏墙面才能穿过去。
小雪希望知道,如果他们要相见,至少要破坏掉多少堵墙?他们可以在任何位置相见。
输入输出格式
输入格式:
第一行有一个整数 N,表示有多少堵墙,保证 0<=N<=8000。
之后 N 行,每一行有三个整数 x, y 和 r,表示有一堵环状的墙是以(x,y)为圆形, r为半径的。保证-100000000<=x,y,r<=100000000。
再下一行有一个整数 Q,表示有多少组询问,保证 1<=Q<=8000。
之后 Q 行,每一行有 4 个整数 a, b, c 和 d,给出了一组询问,表示小雪所在的位置为(a,b),小可可所在的位置为(c,d)。保证-100000000<=a,b,c,d<=100000000。
输出格式:
输出 Q 行,对应 Q 次询问,每一行输出一个整数,表示最小需要破坏掉多少堵墙才能相见。
输入输出样例
说明
对于 20%的数据, 0<=N<=200。
对于 40%的数据, 0<=N<=1000。
对于 100%的数据, 0<=N<=8000, 0<=Q<=8000。
此外,还有额外的 20%的数据,满足 0<=N<=1000, 0<=Q<=1000。
所有数绝对值不超过 100000000。
大数据点时限3s。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
double x,y,r;
}a[];
int n,ans;
double x1,x2,y1,y2;
int main()
{int i,Q;
cin>>n;
for (i=;i<=n;i++)
{
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
}
cin>>Q;
while (Q--)
{
cin>>x1>>y1>>x2>>y2;
ans=;
for (i=;i<=n;i++)
{
int b1=,b2=;
if ((a[i].x-x1)*(a[i].x-x1)+(a[i].y-y1)*(a[i].y-y1)<=a[i].r*a[i].r) b1=;
if ((a[i].x-x2)*(a[i].x-x2)+(a[i].y-y2)*(a[i].y-y2)<=a[i].r*a[i].r) b2=;
if (b1!=b2) ans++;
}
cout<<ans<<endl;
}
}
最新文章
- JS:event对象下的target属性和取消冒泡事件
- 设置button键隐藏文字text
- stm8的IIC库的使用
- VC++中开发汇编语言(转)
- Centos: 修改 yum安装的mysql路径
- PYTHON 迭代器
- no-jquery 01Elements
- EhReport ,CReport改进版本,再次改进 ,V1.31
- Javascript入门学习
- Nginx和PHP-FPM的启动/重启脚本 [转发]
- (转)分布式搜索Elasticsearch——配置
- hdoj 1977 Consecutive sum II
- spark1.3.1使用基础教程
- 基于Emgu CV+百度人脸识别,实现视频动态 人脸抓取与识别
- 【learning】二分图最大匹配的K&#246;nig定理
- python解决图的最短路径问题
- linux下用python搭建简单的httpServer
- Linux----面试
- linux设置开机同步时间
- MYSQL-不能创建表