题目来源:
http://acm.hdu.edu.cn/showproblem.php?pid=1086
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s):
6563 Accepted Submission(s):
3167
分析:
完全是模板
代码如下:
#include <cstdlib> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> #include <iostream> #include <vector> using namespace std; typedef long long ll; double EPS=1e-10; // 考虑误差的加法运算 double add(double a,double b) { if(fabs(a+b)<EPS*(fabs(a)+fabs(b))) return 0; return a+b; } struct Point{ double x,y; Point(){} Point(double x,double y):x(x),y(y){} // 构造函数,方便代码编写 Point operator +(Point p){ return Point(add(x,p.x), add(y,p.y)); } Point operator-(Point p){ return Point(add(x,-p.x),add(y,-p.y)); } Point operator*(double d){ return Point(x*d,y*d); } double dot(Point p){ // 内积 点乘 return add(x*p.x, y*p.y); } double xmult(Point p){// 外积 叉乘 return add(x*p.y,-y*p.x); } }; //判断点p0是否在线段p1p2内 int on_segment(Point p1, Point p2, Point p0) { if (((p1-p0).x * (p2-p0).x <=0 )&& ((p1-p0).y * (p2-p0).y <=0)) // 中间是 && return 1; return 0; } // 判断线段是否相交 int intersection(Point p1,Point p2, Point q1,Point q2) { double d1=(p2-p1).xmult(q1-p1); // 计算p1p2 到q 点的转向 d1>0 左转, d1 <0 右转 double d2=(p2-p1).xmult(q2-p1); double d3=(q2-q1).xmult(p1-q1); double d4=(q2-q1).xmult(p2-q1); if((d1==0 && on_segment(p1,p2,q1) )|| (d2==0 && on_segment(p1,p2,q2) )|| (d3==0&& on_segment(q1,q2,p1)) || (d4==0 && on_segment(q1,q2,p2))) return 1; else if(d1*d2<0 && d3*d4 <0) // 中间是 && return 1; return 0; } int main() { int t,sum; Point p1[105],p2[105]; while(cin>>t&&t) { sum=0; for(int i=0;i<t;i++) { cin>>p1[i].x>>p1[i].y>>p2[i].x>>p2[i].y; } for(int i=0;i<t;i++) for(int j=i+1;j<t;j++) sum+=intersection(p1[i],p2[i],p1[j],p2[j]); cout<<sum<<endl; } return 0; }
hdu 1086 计算几何 求线段有多少个交点,布布扣,bubuko.com
原文:http://www.cnblogs.com/zn505119020/p/3616884.html