首页 > 代码库 > [haoi2014]穿越封锁线
[haoi2014]穿越封锁线
这题需要注意的一点是射线法需要考虑边界,而且题目对边界的限制极为严格.
dcmp(v[i%n].x-x)<=0&&dcmp(v[(i+1)%n].x-x)>0 dcmp(v[i%n].x-x)>0&&dcmp(v[(i+1)%n].x-x)<=0
这是我写的版本.
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<queue> #include<set> #include<map> #include<iomanip> using namespace std; #define LL long long #define up(i,j,n) for(int i=j;i<=n;i++) #define pii pair<int,int> #define db double #define eps 1e-4 #define FILE "dealing" int read(){ int x=0,f=1,ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar();} return x*f; } const int maxn=22000,inf=1000000000; bool cmin(db& a,db b){return a>b?a=b,true:false;} int n; struct vec { db x,y; vec(db x=0,db y=0):x(x),y(y){} }v[maxn]; int dcmp(db v){if(fabs(v)<eps)return 0;return v<0?-1:1;} db x,y; db s[5]; db gety(vec v,vec b,db x){ db k=(b.y-v.y)/(b.x-v.x); db d=v.y-v.x*k; return x*k+d; } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); up(i,0,n-1)v[i].x=read(),v[i].y=read(); x=read(),y=read(); int wn=1;db ans=0,last=y; db Min=inf;int k=0; up(i,0,n-1) if(((v[i%n].x<x&&v[(i+1)%n].x>x)||(v[i%n].x>x&&v[(i+1)%n].x<x))&&gety(v[i%n],v[(i+1)%n],x)>y&&cmin(Min,gety(v[i],v[(i+1)%n],x)-y)){k=i;} up(i,k,k+n-1){ if(dcmp(v[i%n].x-x)<=0&&dcmp(v[(i+1)%n].x-x)>0&&dcmp(gety(v[i%n],v[(i+1)%n],x)-y)>0){ s[wn]+=gety(v[i%n],v[(i+1)%n],x)-last; last=gety(v[i%n],v[(i+1)%n],x); wn++; } else if(dcmp(v[i%n].x-x)>0&&dcmp(v[(i+1)%n].x-x)<=0&&dcmp(gety(v[i%n],v[(i+1)%n],x)-y)>0){ s[wn]+=gety(v[i%n],v[(i+1)%n],x)-last; last=gety(v[i%n],v[(i+1)%n],x); wn--; } } if(wn==1)printf("%d\n",(int)fabs(s[2]+s[0])); else printf("%d\n",fabs(s[1])); return 0; }
[haoi2014]穿越封锁线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。