首页 > 代码库 > NYOJ_83:迷宫寻宝(二)(计算几何)
NYOJ_83:迷宫寻宝(二)(计算几何)
题目链接
枚举所有墙的2n个端点与宝物的位置作为一条线段(墙的端点必定与边界重合), 求出与之相交的最少线段数(判断线段相交时用跨立实验的方法),+1即为结果。
#include<bits/stdc++.h> using namespace std; struct point { double x,y; point operator -(const point& rhs)const { point ret; ret.x=x-rhs.x; ret.y=y-rhs.y; return ret; } double operator *(const point& rhs)const//叉乘 { return x*rhs.y-y*rhs.x; } bool operator <(const point& rhs)const { return x<rhs.x||x==rhs.x&&y<rhs.y; } } la[105],lb[105],en; int n; bool ok(point a,point b,point c,point d) { return ((b-a)*(c-a))*((b-a)*(d-a))<0; } int cal(point A,point B) { int ret=0; for(int i=0; i<n; i++) if(ok(la[i],lb[i],A,B)) ret++; return ret; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); if(n<3) { puts("1"); //边界占一个 continue; } for(int i=0; i<n; i++) scanf("%lf%lf%lf%lf",&la[i].x,&la[i].y,&lb[i].x,&lb[i].y); scanf("%lf%lf",&en.x,&en.y); int ans=1000; for(int i=0; i<n; i++) { ans=min(ans,cal(en,la[i])); ans=min(ans,cal(en,lb[i])); } printf("%d\n",ans+1); } }
NYOJ_83:迷宫寻宝(二)(计算几何)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。