首页 > 代码库 > bzoj4814: [Cqoi2017]小Q的草稿
bzoj4814: [Cqoi2017]小Q的草稿
Description
小Q是个程序员。众所周知，程序员在写程序的时候经常需要草稿纸。小Q现在需要一张草稿纸用来画图，但是桌上
只有一张草稿纸，而且是一张被用过很多次的草稿纸。草稿纸可以看作一个二维平面，小Q甚至已经给它建立了直
角坐标系。以前每一次草稿使用过的区域，都可以近似的看作一个平面上的一个三角形，这个三角形区域的内部和
边界都不能再使用。当然了，以前的草稿也没有出现区域重叠的情况。小Q已经在草稿纸上画上了一些关键点，这
些关键点都在没使用过的区域。小Q想把这些关键点两两之间尽可能的用线段连接起来。连接两个关键点的线段有
可能会穿过已经用过的草稿区域，这样显然不允许。于是小Q就想知道，有多少对关键点可以被线段连接起来，而
且还不会穿过已经用过的区域。为了方便，小Q保证任意三个关键点不会共线。
Input
第一行包含两个整数V,T,表示草稿纸上的关键点数量和三角形区域数量。
接下来V行，每行两个整数x,y,表示一个关键点的坐标(x,y)。
接下来T行，每行六个整数x1,y1,x2,y2,x3,y3,表示一个三角形区域的三个顶点坐标分别是(x1,y1),(x2,y2),(x3,y
3)保证三角形的面积大于0。
V<=1000,T<=1000,0<=所有坐标<=10^8且为整数
Output
输出一行，一个整数，表示能够被线段连接起来的关键点有多少对。
对每个点以它为中心进行扫描线，处理在右方的点和三角形。
#include<bits/stdc++.h>typedef long long i64;typedef double ld;int n,m;int sgn(i64 x){return x<0?-1:x>0;}struct pos{ int x,y; void R(){scanf("%d%d",&x,&y);} i64 pw2(){return i64(x)*x+i64(y)*y;}}ps[1007],ws[1007],trs[1007][3],O=(pos){0,0},now;pos operator-(const pos&a,const pos&b){return (pos){a.x-b.x,a.y-b.y};}int operator*(const pos&a,const pos&b){return sgn(i64(a.x)*b.y-i64(a.y)*b.x);}ld mul(const pos&a,const pos&b){return ld(a.x)*b.y-ld(a.y)*b.x;}bool cmp(const pos&a,const pos&b){return a.x!=b.x?a.x<b.x:a.y<b.y;}bool operator<(const pos&a,const pos&b){return a*b<0;}struct seg{ pos a[2]; ld val()const{return mul(a[0],a[1])/mul(now,a[1]-a[0]);} bool operator<(const seg&w)const{return val()<w.val();}};std::set<seg>st;std::set<seg>::iterator its[2007];struct Q{ pos a[2]; int t,id; bool operator<(const Q&w)const{ int x=a[t]*w.a[w.t]; return x?x<0:t<w.t; } bool operator<(const pos&w){ int x=a[t]*w; return x?x<0:!t; } void cal(){ now=a[t]; if(cmp(now,O))now=(pos){0,1}; if(t)st.erase(its[id]); else{ seg s=(seg){a[0],a[1]}; its[id]=st.insert(s).first; } }}qs[2007];bool cross(pos a,pos b1,pos b2){ pos ba=b2-a; if((a*(b1-a))*(a*ba)>0)return 0; pos b3=b1-b2; return (b3*b2)*(b3*ba)<=0;}int ans=0,wp,qp,ip;void scl(){ for(int i=0,j=0;i<wp;++i){ for(;j<qp&&qs[j]<ws[i];qs[j++].cal()); if(st.empty()||!cross(ws[i],st.begin()->a[0],st.begin()->a[1]))++ans; }}void aq(pos a,pos b){ bool da=cmp(O,a),db=cmp(O,b); ++ip; if(da)qs[qp++]=(Q){a,b,0,ip}; else if(db)((Q){a,b,0,ip}).cal(); if(db)qs[qp++]=(Q){a,b,1,ip};}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)ps[i].R(); std::sort(ps+1,ps+n+1,cmp); for(int i=1;i<=m;++i)for(int j=0;j<3;++j)trs[i][j].R(); for(int i=1;i<=n;++i){ st.clear(); wp=0,qp=0,ip=0; for(int j=i+1;j<=n;++j)ws[wp++]=ps[j]-ps[i]; std::sort(ws,ws+wp); for(int j=1;j<=m;++j){ pos tr[3]; for(int t=0;t<3;++t)tr[t]=trs[j][t]-ps[i]; std::sort(tr,tr+3); aq(tr[0],tr[2]); } std::sort(qs,qs+qp); scl(); } printf("%d\n",ans); return 0;}
bzoj4814: [Cqoi2017]小Q的草稿
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。