题目连接:uva 1421&uvalive
4253Archery
题目大意:有n个平行与x轴的线段,每条线段代表一个靶子。你的任务是判断是否可以站在x轴上[0,w]区间的某个位置射箭,使得箭能穿过所有靶子。
解题思路:二分人站的位置,对于每个位置,维护靶子的可以击中的角度,如果出现靶子的区间,l > R,人左移;r < L人右移。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
const int N = 5005;
const double esp = 1e-6;
int n, t;
double w;
struct Seg {
double d, l, r;
}s[N];
bool cmp(Seg a, Seg b) {
return a.d < b.d;
}
int judge(double x) {
double L = atan2(s[0].d, s[0].r - x);
double R = atan2(s[0].d, s[0].l - x);
for (int i = 1; i < n; i++) {
double l = atan2(s[i].d, s[i].r - x);
double r = atan2(s[i].d, s[i].l - x);
if (r - L < -esp)
return -1;
if (l - R > esp)
return 1;
L = max(L, l);
R = min(R, r);
}
return 0;
}
bool solve () {
sort(s, s + n, cmp);
double l = 0, r = w;
while (r - l > esp) {
double mid = (l+r)/2;
int k = judge(mid);
if (k == 0) return true;
else if (k == -1) r = mid;
else l = mid;
}
return false;
}
int main () {
scanf("%d", &t);
while (t--) {
scanf("%lf%d", &w, &n);
for (int i = 0; i < n; i++)
scanf("%lf%lf%lf", &s[i].d, &s[i].l, &s[i].r);
printf("%s\n", solve() ? "YES" : "NO");
}
return 0;
}
分享到:
相关推荐
Archery
介绍了archery功能及详细配置过程。 包含sql审核案例,sql分析及优化案例,实例管理案例,插件案例等
sql审核平台archery配置文档
Archery-master.zip
涉及Archery的相关安装包
在使用该模块之前,必须创建一个环境变量ARCHERY_PERSON_SECRET ,该变量可以位于项目内部的.env文件中。此密钥必须为32个url-safe base64编码的字节。 >> > from archery_secret import Secret >> > >> > >> > ...
内容简介: 为了追求在哲学中无法得到的生命意义,作者远渡重洋来到东方的日本学禅,处处碰壁之后,透过箭术,他体验了禅的真义。他将这段曲折的学习经验,生动地记录下来,篇幅虽短,却难能可贵地以文字传递了不...
语言:English,English (UK),English (United States) archery是一个经典的弓箭射击游戏,瞄准目标板并拍摄获得高分。 *游戏说明** 将鼠标移动并在目标处箭头。
Archery 定位于 SQL 审核查询平台,旨在提升 DBA 的工作效率,支持多种数据库的 SQL 上线和查询,同时支持丰富的MySQL运维功能,所有功能都兼容手机端操作。 启动: 下载 Releases文件,解压后进入docker-compose...
Archery Blast 射箭爆炸Unity休闲射击游戏项目源码C# 商品描述 支持Unity版本2018.2.0f2及以上 弓箭手……向你鞠躬!在《Archery Blast》中,您是一名有抱负的弓箭手,接受更疯狂的挑战!这次有60个挑战等着你!您将...
Archery SQL审核查询平台 v1.10.0.zip
## Archery SQL审核查询平台 ###Description: Archery 定位于 SQL 审核查询平台,旨在提升 DBA 的工作效率,支持多种数据库的 SQL 上线和查询,同时支持丰富的MySQL运维功能,所有功能都兼容手机端操作。启动:...
SQL 审核查询平台
Learning the skill of archery by a humanoid robot iCub [EN] IROS2010
Archery Clash 商品描述 这是射箭比赛。 瞄准并射击。 那些想要创建射箭游戏的人那么这个资源适合您。 尝试用弓箭击落所有灯笼和花瓶。您必须击中所有标有大红点的项目。探索各种日式花园,花点时间拉紧弓弦,做好...
https://pytorchvideo.org/docs/tutorial_torchhub_inference#load-an-example-video archery.mp4 pytorchvideo demo演示视频
archive_ Archery SQL审核查询平台 v1.9.1 [江西新余电信].zip.zip
射箭是一个经典的弓箭射击游戏,瞄准目标板并射击获得高分。 *游戏说明**移动鼠标并将箭头对准目标。 支持语言:English,English (UK),English (United States)
射箭人 授权和会话管理器。