首页 > 代码库 > 线段交点模版
线段交点模版
http://acm.hdu.edu.cn/showproblem.php?pid=1086
跨立实验算法
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; struct Point { double x,y; } ; struct Line { Point s,e; }; Line arr[105]; double Chacheng(Point a,Point b,Point c) { return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y); } int is_across(Line a,Line b) { if(max(a.s.x,a.e.x)>=min(b.s.x,b.e.x)&& max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&& max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&& Chacheng(b.s,a.e,a.s)*Chacheng(a.e,b.e,a.s)>=0&& Chacheng(a.s,b.e,b.s)*Chacheng(b.e,a.e,b.s)>=0) return 1; return 0; } int main() { //freopen("in.txt","r",stdin); int n; while(scanf("%d",&n)&&n) { int ans=0; for(int i=0;i<n;i++) scanf("%lf %lf %lf %lf",&arr[i].s.x,&arr[i].s.y, &arr[i].e.x,&arr[i].e.y); for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) if(is_across(arr[i],arr[j])) ans++; printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。