Printed Circuit Board (board)

2023-09-01 04:49:49

Printed Circuit Board (board)

题目描述

给出一个N个顶点的简单多边形，对于每个顶点，假如它和原点连成的线段只在这个顶点处和多边形相交，就称为满足要求的顶点。你的任务是输出所有满足要求的顶点编号。

输入

第一行一个正整数N。下面N行每行两个不超过10e6的正整数，依次表示每个顶点的坐标。顶点按照输入顺序用正整数1..N编号，并且顶点保证按照顺时针或逆时针顺序给出。

输出

第一行一个正整数M，表示满足要求的顶点个数。第二行M个正整数，按照升序给出满足要求的顶点编号。

solution

计算几何好题

首先我们按极角把点离散化了。

一条条加入边，判断覆盖一个点的边是不是他的临边就是答案

注意到覆盖区间时没必要覆盖到底，打在区间上即可，查询时一路统计答案。

那么·还剩一个问题，怎么判断两条边谁前谁后。

我们用

第一条边y较小的和第二条边y较大的

第一条边y较大的和第二条边y较小的

叉积起来

画画图就可以发现了

有一个细节，相同斜率的点其实不用特判。

因为那些点怎么都不会被覆盖。

#include
#include
#include
#include
#include
#include
#include
#define db double
#define ll long long
#define maxn 200005
#define inf 1e9
using namespace std;
int n,tot,li,ri,ans[maxn],flag[maxn],t;
struct node{int x,y,id;db k;
}s[maxn];
int tr[maxn*4];
mapl;
bool cmp(node a,node b){return a.kp2.k)swap(p1,p2);if(p3.k>p4.k)swap(p3,p4);node A=xl(p1,p4),B=xl(p2,p3);if(cr(A,B)<0)return 0;//a close else return 1;
}
void update(int &x,int now){if(!x)x=now;else if(pd(x,now))x=now;
}
void add(int k,int l,int r,int id){if(l>=li&&r<=ri){update(tr[k],id);return;}int mid=l+r>>1;if(li<=mid)add(k*2,l,mid,id);if(ri>mid)add(k*2+1,mid+1,r,id);
}
void ask(int k,int l,int r,int pl){if(tr[k])update(t,tr[k]);if(l==r)return;int mid=l+r>>1;if(pl<=mid)ask(k*2,l,mid,pl);else ask(k*2+1,mid+1,r,pl);
}
int main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&s[i].x,&s[i].y);s[i].id=i;if(!s[i].x)s[i].k=inf;else s[i].k=(db)s[i].y/(db)s[i].x;}sort(s+1,s+n+1,cmp);s[0].k=-1;for(int i=1;i<=n;i++){if(s[i].k==s[i-1].k){flag[s[i].id]=1;continue;}l[s[i].k]=++tot;}sort(s+1,s+n+1,C);for(int i=1;i<=n;i++){li=l[s[i].k],ri=l[s[i+1].k];int D=i;if(i==n)ri=l[s[1].k];if(li>ri)swap(li,ri);add(1,1,n,i);}for(int i=1;i<=n;i++){t=0;ask(1,1,n,l[s[i].k]);if(i==1){if(t==n||t==1)ans[i]=1;}else {if(t==i||t==i-1)ans[i]=1;}}int sum=0;for(int i=1;i<=n;i++){if(flag[i])continue;if(ans[i])sum++;}cout<

  
             posted @ 2018-11-30 20:16 liankewei 阅读( ...) 评论( ...) 编辑 收藏                        
                        
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！



                    



                    

    收藏
    



                    
    
        
        标签：技术
        
    

    
        
                
            上一篇 >
            PCB设计中专业英译术语之综合词汇（基础介绍）
        
                
            下一篇 >
            Android程序之聚合数据全国天气预报查询API接口使用演示
        
                
    



                    
    
        
        
            相关文章
        
                
            Duilib中list控件支持ctrl和shif多行选中的实现
        
                
            [ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif
        
                
            win10系统 微软输入法 于eclipse ctrl+shif+f冲突间接处理办法
        
                
            Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif
        
                
            读LDD3，内存映射与DMA--PAGE_SHIF…
        
                
            VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】
        
                
            更换iBus五笔的左与右Shif
        
                
            sublime ctrl+shif+f 没用解决办法
        
                
            idea 对 ctrl + z 的撤销 是 ctrl + shif + z
        
                
            计算机最早的设计师应用于,计算机应用基础选择题doc.doc
        
                
            win10自带截图神器：Win+Shift+S
        
                
            Python基础之文件目录操作
        
                
            python简述目录_Python基础之文件目录操作(示例代码)
        
                
            tp5 如何做数据采集
        
                
            任务2-7(服务器字体+阿里巴巴矢量库)
        
                
            html标签（1)：h1~h6,p,br,pre,hr
        
                
            TI 电量计介绍与芯片选型指南
        
                
            几款TI电源芯片简介
        
                
            TI DSP芯片C2000系列读取FLASH数据
        
                
            德州仪器(Ti)平台嵌入式开发基础
        
                
            TI三相电机智能栅极驱动芯片特点分类
        
                
            省选模拟（12.08） T3 圈圈圈圈圈圈圈圈
        
                
            Hadoop生态圈技术栈（上）
        
                
            大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询
        
                
            小猿圈之Linux下Mysql 操作命令
        
                
            大数据Hadoop生态圈常用面试题
        
                
            大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作
        
                
            备战Noip2018模拟赛11（B组）T3 Monogatari 物语
        
                
            【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码
        
                
            NYOJ 78 圈水池
        
                
            递归问题 跑道 汽车 绕圈问题 Python实现
        
                
            Hadoop生态圈（三）：MapReduce