【2020NIO.AC省选模拟#10】C. 寄蒜几盒
2024-09-08 19:35:42
题目链接
原题解:
可以发现,假设我们把凸多边形看做障碍,一个点没有被染色当且仅当在它的位置上能看到凸多边形任意两条相对的边中的一条(也就是能看到至少$\dfrac{n}{2}$条边)。
对于每个询问点,我们只需要从某个点出发二分出能看到或不能看到的边的区间,就能知道它有没有被染色。
(可以使用__int128)
补充:
虽然有直线划分,但本题并不是用半平面交做。
代码(100分):
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define IL inline
#define RG register
using namespace std;
typedef long long LL;
typedef __int128 Int;
#define RI RG int
#define RC RG char
const int N=1e5; int L,R,i,l,m,n,o,q,r,s,t;
LL a[N],b[N],x,y; IL bool cmp(RI u,RI v){
return (Int)0<=(Int)(a[u]-x)*(b[v]-y)
-(Int)(a[v]-x)*(b[u]-y);
} IL bool solve(){
scanf("%lld%lld",&x,&y);
x^=(LL)t*s*s*s;
y^=(LL)t*s*s*s;
o=cmp(n>>1,(n>>1)+1);
if(o==cmp(n,1))
return o; for(l=1,r=n>>1;l<r;){
m=l+r>>1;
cmp(m,m+1)^o?l=m+1:r=m; }
for(L=l,l=n>>1,r=n-1;l<r;){
m=l+r+2>>1;
cmp(m,m+1)^o?r=m-1:l=m; } R=l;
if(o)
return (n>>1)<R-L+1;
else
return R-L+1<(n>>1); } int main(){
scanf("%d%d",&t,&n);
for(RI i=1;i<=n;i++)
scanf("%lld%lld",&a[i],&b[i]);
scanf("%d",&q);
for(RI i=1;i<=q;i++){
s+=o=solve();
puts(o?"DA":"NE"); } return 0; }
最新文章
- 在Java filter中调用service层方法
- GIT简单操作
- ios二维码扫描
- 将war包部署到服务器的详细步骤
- 浅谈设计模式--单例模式(Singleton Pattern)
- 部署搭建 Saltstack(centos6.6)
- XML学习笔记(二)-- DTD格式规范
- Redis基础知识之————如何处理客户端连接
- poj 1631 Bridging signals (二分||DP||最长递增子序列)
- R语言从小木虫网页批量提取考研调剂信息
- Junit4学习(四)Junit4常用注解
- java类定义、变量类型、构造函数
- 初学JSP
- Redis详解(一)------ redis的简介与安装
- LVM方式安装Ubuntu 系统
- 网站JS控制的QQ悬浮
- 读取excel日期数据问题
- RichEdit文字背景色的处理
- Scrapy学习篇(四)之数据存储
- MVC 在action方法中获取当前action的控制器名和action名
热门文章
- 浅谈dfs深度优先搜索
- Python的入门学习之Day 9——from“夜曲编程”
- linux下安装jdk8,nginx
- Generamba构建模板,让开发变得更高效
- 【服务器数据恢复】热备盘同步失败导致数据丢失的raid5数据恢复案例
- MxDraw云图平台 2021.10.28更新,H5在线CAD,网页CAD,网页浏览编辑DWG
- 【运维】解决composer update出现的Discard changes [y,n,v,d,s,?]的问题
- 《计算机是怎么跑起来的》第十章 XML(可扩展标记语言)
- ERROR 1862 (HY000): Your password has expired. To log in you must change it using a .....
- MySQL表操作(上篇)