Hint：输出要用%f，最好不要%lf，特别是poj上

模板：

#include<bits/stdc++.h>
using namespace std;
typedef double D;
const D eps=1e-8,inf=1e99;
int sgn(D x){
    if (fabs(x)<eps) return 0;
    if (x>0) return 1;
    return -1;
}
struct P{
    D x,y;
    P(){};
    P(D xx,D yy){x=xx;y=yy;}
    friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
    friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
    friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
    friend D operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
	friend void get_line(P p1,P p2,D &a,D &b,D &c){a=p2.y-p1.y;b=p1.x-p2.x;c=-p1.x*a-p1.y*b;}
	friend P get_inter(P p1,P p2,P p3,P p4){
    	D a1,b1,c1,a2,b2,c2,d;
    	get_line(p1,p2,a1,b1,c1);
    	get_line(p3,p4,a2,b2,c2);
    	P p5=P(inf,inf);
    	if (sgn(a1)==0 && sgn(a2)==0 || sgn(b1)==0 && sgn(b2)==0) return p5;
    	if (sgn(b1)!=0 && sgn(b2)!=0 && sgn(a1/b1-a2/b2)==0) return p5;
    	d=a1*b2-a2*b1;
    	p5=P((b1*c2-b2*c1)/d,(a2*c1-a1*c2)/d);
    	return p5;
	}
	friend D dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
	friend bool on_seg(P p1,P p2,P p){
    	return dir(p,p1,p2)==0 && min(p1.x,p2.x)<=p.x && p.x<=max(p1.x,p2.x)
    	&& min(p1.y,p2.y)<=p.y && p.y<=max(p1.y,p2.y);
	}
	friend bool judge_inter(P p1,P p2,P p3,P p4){
    	P p=get_inter(p1,p2,p3,p4);
    	return on_seg(p1,p2,p) && on_seg(p3,p4,p);
	}
	friend bool check_inter(P p1,P p2,P p3,P p4){
    	if (max(p1.x,p2.x)<min(p3.x,p4.x) || min(p1.x,p2.x)>max(p3.x,p4.x) ||
        	max(p1.y,p2.y)<min(p3.y,p4.y) || min(p1.y,p2.y)>max(p3.y,p4.y)) return 0;
   		D d1=dir(p3,p4,p1),d2=dir(p3,p4,p2),d3=dir(p1,p2,p3),d4=dir(p1,p2,p4);
    	if (d1*d2<0 && d3*d4<0) return 1;
    	return sgn(d1)==0 && on_seg(p3,p4,p1) || sgn(d2)==0 && on_seg(p3,p4,p2) ||
    	       sgn(d3)==0 && on_seg(p1,p2,p3) || sgn(d4)==0 && on_seg(p1,p2,p4);
	}
	friend D dis(P p1,P p2){P p=(p1-p2)*(p1-p2);return sqrt(p.x+p.y);}
};
struct L{
    P p1,p2;
    L(){};
    L(P xx,P yy){p1=xx;p2=yy;}
	friend D len(L l){P p=(l.p1-l.p2)*(l.p1-l.p2);return sqrt(p.x+p.y);}
	friend void getline(L l,D &a,D &b,D &c){get_line(l.p1,l.p2,a,b,c);}
	friend P getinter(L l1,L l2){return get_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
	friend bool onseg(L l,P p){return on_seg(l.p1,l.p2,p);}
	friend D dirl(P p,L l){return dir(p,l.p1,l.p2);}
	friend bool judgeinter(L l1,L l2){return judge_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
	friend bool checkinter(L l1,L l2){return check_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
};

foj1015 土地划分

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,i,ans,j,r,c;
struct P{
	int x,y;
	P(){};
	P(int xx,int yy){x=xx;y=yy;}
	friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
	friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
	friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
}a[52];
int det(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
bool on_seg(P p1,P p2,P p){
	return min(p1.x,p2.x)<=p.x && p.x<=max(p1.x,p2.x) && min(p1.y,p2.y)<=p.y && p.y<=max(p1.y,p2.y);
}
int dir(P p,P p1,P p2){return det(p-p1,p-p2);}
bool check_inter(P p1,P p2,P p3,P p4){
	if (max(p1.x,p2.x)<min(p3.x,p4.x) || min(p1.x,p2.x)>max(p3.x,p4.x) ||
		max(p1.y,p2.y)<min(p3.y,p4.y) || min(p1.y,p2.y)>max(p3.y,p4.y)) return 0;
	int d1=dir(p3,p4,p1),d2=dir(p3,p4,p2),d3=dir(p1,p2,p3),d4=dir(p1,p2,p4);
	if (d1*d2<0 && d3*d4<0) return 1;
	return 0;
}
int main(){
	while (~scanf("%d%d",&r,&c) && r && c){
		scanf("%d",&n);
		for (i=0;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
		ans=n+1;
		for (i=2;i<=n;i++)
			for (j=0;j<i;j++) ans+=check_inter(a[i-1],a[i],a[j],a[j+1]);
		printf("%d\n",ans);
	}
}

POJ 2318 TOYS

#include<cstdio>
#include<cstring>
using namespace std;
const int N=5002;
int n,m,i,x1,x2,y1,y2,u,L,cnt[N],x,y,l,r,mid,fl,tmp;
struct P{
	int x,y;
	P(){};
	P(int xx,int yy){x=xx;y=yy;}
	friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
	friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
	friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
	friend int operator ^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
}a[N],b[N],p;
int dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
int main(){
	while (~scanf("%d",&n) && n){
		if (fl) puts("");
		fl=1;
		scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
		for (i=0;i<n;i++) scanf("%d%d",&u,&L),a[i]=P(u,y1),b[i]=P(L,y2);
		a[n]=P(x2,y1);b[n]=P(x2,y2);
		memset(cnt,0,sizeof(cnt));
		while (m--){
			scanf("%d%d",&x,&y);
			p=P(x,y);
			l=0;r=n;
			while (l<=r){
				mid=l+r>>1;
				if (dir(p,a[mid],b[mid])<0) r=mid-1,tmp=mid;
				else l=mid+1;
			}
			cnt[tmp]++;
		}
		for (i=0;i<=n;i++) printf("%d: %d\n",i,cnt[i]);
	}
}

POJ 3304 Segments

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double D;
const D eps=1e-8,inf=1e99;
int n,i,j,T,fl;
//point start
struct P{
	D x,y;
	P(){};
	P(D xx,D yy){x=xx;y=yy;}
	friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
	friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
	friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
	friend D operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
};
void get_line(P p1,P p2,D &a,D &b,D &c){a=p2.y-p1.y;b=p1.x-p2.x;c=-p1.x*a-p1.y*b;}
P get_inter(P p1,P p2,P p3,P p4){
	D a1,b1,c1,a2,b2,c2,d;
	get_line(p1,p2,a1,b1,c1);
	get_line(p3,p4,a2,b2,c2);
	P p5=P(inf,inf);
	if (fabs(a1)<eps && fabs(a2)<eps || fabs(b1)<eps && fabs(b2)<eps) return p5;
	if (fabs(b1)>eps && fabs(b2)>eps && fabs(a1/b1-a2/b2)<eps) return p5;
	d=a1*b2-a2*b1;
	p5=P((b1*c2-b2*c1)/d,(a2*c1-a1*c2)/d);
	return p5;
}
bool on_seg(P p1,P p2,P p){return min(p1.x,p2.x)<=p.x && p.x<=max(p1.x,p2.x) && min(p1.y,p2.y)<=p.y && p.y<=max(p1.y,p2.y);}
D dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
bool judge_inter(P p1,P p2,P p3,P p4){
	P p=get_inter(p1,p2,p3,p4);
	return on_seg(p1,p2,p) && on_seg(p3,p4,p);
}
bool check_inter(P p1,P p2,P p3,P p4){
	if (max(p1.x,p2.x)<min(p3.x,p4.x) || min(p1.x,p2.x)>max(p3.x,p4.x) ||
		max(p1.y,p2.y)<min(p3.y,p4.y) || min(p1.y,p2.y)>max(p3.y,p4.y)) return 0;
	D d1=dir(p3,p4,p1),d2=dir(p3,p4,p2),d3=dir(p1,p2,p3),d4=dir(p1,p2,p4);
	if (d1*d2<0 && d3*d4<0) return 1;
	return fabs(d1)<eps && on_seg(p3,p4,p1) || fabs(d2)<eps && on_seg(p3,p4,p2) ||
		   fabs(d3)<eps && on_seg(p1,p2,p3) || fabs(d4)<eps && on_seg(p1,p2,p4);
}
D dis(P p1,P p2){P p=(p1-p2)*(p1-p2);return sqrt(p.x+p.y);}
//point end
//line start
struct L{
	P p1,p2;
	L(){};
	L(P xx,P yy){p1=xx;p2=yy;}
}a[102];
D len(L l){P p=(l.p1-l.p2)*(l.p1-l.p2);return sqrt(p.x+p.y);}
void getline(L l,D &a,D &b,D &c){get_line(l.p1,l.p2,a,b,c);}
P getinter(L l1,L l2){return get_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
bool onseg(L l,P p){return on_seg(l.p1,l.p2,p);}
D dirl(P p,L l){return dir(p,l.p1,l.p2);}
bool judgeinter(L l1,L l2){return judge_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
bool checkinter(L l1,L l2){return check_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
//line end
bool chkinter(L l1,L l2){return dirl(l2.p1,l1)*dirl(l2.p2,l1)<eps;}
bool check(L l){
	if (fabs(len(l))<eps) return 0;
	for (int i=0;i<n;i++)
		if (!chkinter(l,a[i])) return 0;
	return 1;
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		for (i=0;i<n;i++) scanf("%lf%lf%lf%lf",&a[i].p1.x,&a[i].p1.y,&a[i].p2.x,&a[i].p2.y);
		fl=0;
		for (i=0;i<n && !fl;i++)
			for (j=0;j<n && !fl;j++)
				if (check(L(a[i].p1,a[j].p1)) || check(L(a[i].p1,a[j].p2))
				 || check(L(a[i].p2,a[j].p1)) || check(L(a[i].p2,a[j].p2))) fl=1;
		puts(fl?"Yes!":"No!");
	}
}

POJ 1269 Intersecting Lines

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double D;
const D eps=1e-6,inf=1e9999;
int T;
//point start
struct P{
	D x,y;
	P(){};
	P(D xx,D yy){x=xx;y=yy;}
	friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
	friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
	friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
	friend D operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
}p;
int sgn(D x){
	if (fabs(x)<eps) return 0;
	if (x>0) return 1;
	return -1;
}
void get_line(P p1,P p2,D &a,D &b,D &c){a=p2.y-p1.y;b=p1.x-p2.x;c=-p1.x*a-p1.y*b;}
P get_inter(P p1,P p2,P p3,P p4){
	D a1,b1,c1,a2,b2,c2,d;
	get_line(p1,p2,a1,b1,c1);
	get_line(p3,p4,a2,b2,c2);
	P p5=P(inf,inf);
	if (sgn(a1)==0 && sgn(a2)==0 || sgn(b1)==0 && sgn(b2)==0) return p5;
	if (sgn(b1)!=0 && sgn(b2)!=0 && sgn(a1/b1-a2/b2)==0) return p5;
	d=a1*b2-a2*b1;
	p5=P((b1*c2-b2*c1)/d,(a2*c1-a1*c2)/d);
	return p5;
}
bool on_seg(P p1,P p2,P p){return min(p1.x,p2.x)<=p.x && p.x<=max(p1.x,p2.x) && min(p1.y,p2.y)<=p.y && p.y<=max(p1.y,p2.y);}
D dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
bool judge_inter(P p1,P p2,P p3,P p4){
	P p=get_inter(p1,p2,p3,p4);
	return on_seg(p1,p2,p) && on_seg(p3,p4,p);
}
bool check_inter(P p1,P p2,P p3,P p4){
	if (max(p1.x,p2.x)<min(p3.x,p4.x) || min(p1.x,p2.x)>max(p3.x,p4.x) ||
		max(p1.y,p2.y)<min(p3.y,p4.y) || min(p1.y,p2.y)>max(p3.y,p4.y)) return 0;
	D d1=dir(p3,p4,p1),d2=dir(p3,p4,p2),d3=dir(p1,p2,p3),d4=dir(p1,p2,p4);
	if (d1*d2<0 && d3*d4<0) return 1;
	return sgn(d1)==0 && on_seg(p3,p4,p1) || sgn(d2)==0 && on_seg(p3,p4,p2) ||
		   sgn(d3)==0 && on_seg(p1,p2,p3) || sgn(d4)==0 && on_seg(p1,p2,p4);
}
D dis(P p1,P p2){P p=(p1-p2)*(p1-p2);return sqrt(p.x+p.y);}
//point end
//line start
struct L{
	P p1,p2;
	L(){};
	L(P xx,P yy){p1=xx;p2=yy;}
}l1,l2;
D len(L l){P p=(l.p1-l.p2)*(l.p1-l.p2);return sqrt(p.x+p.y);}
void getline(L l,D &a,D &b,D &c){get_line(l.p1,l.p2,a,b,c);}
P getinter(L l1,L l2){return get_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
bool onseg(L l,P p){return on_seg(l.p1,l.p2,p);}
D dirl(P p,L l){return dir(p,l.p1,l.p2);}
bool judgeinter(L l1,L l2){return judge_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
bool checkinter(L l1,L l2){return check_inter(l1.p1,l1.p2,l2.p1,l2.p2);}
//line end
int main(){
	puts("INTERSECTING LINES OUTPUT");
	scanf("%d",&T);
	while (T--){
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&l1.p1.x,&l1.p1.y,&l1.p2.x,&l1.p2.y,&l2.p1.x,&l2.p1.y,&l2.p2.x,&l2.p2.y);
		p=getinter(l1,l2);
		if (p.x==inf) puts(sgn(dirl(l1.p1,l2))==0?"LINE":"NONE");
		else printf("POINT %.2f %.2f\n",p.x,p.y);
	}
	puts("END OF OUTPUT");
}

POJ 1696 Space Ant

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double D;
const int N=52;
int n,i,top,st[N],T,k,pos;
struct P{
	int id,x,y;
	P(){};
	P(int iid,int xx,int yy){id=iid;x=xx;y=yy;}
	friend P operator -(P a,P b){return P(0,a.x-b.x,a.y-b.y);}
	friend int operator ^(P a,P b){return a.x*b.y-a.y*b.x;}
}p[N];
int dir(P p,P p1,P p2){return (p1-p)^(p2-p);}
D dis (P p1,P p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
bool cmp(P p1,P p2){
	int t=dir(p[pos],p1,p2);
	return t>0 || t==0 && dis(p[pos],p1)<dis(p[pos],p2);
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		k=0;
		for (i=0;i<n;i++){
			scanf("%d%d%d",&p[i].id,&p[i].x,&p[i].y);
			if (p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
		}
		swap(p[0],p[k]);
		printf("%d %d",n,p[0].id);
		pos=0;
		for (i=1;i<n;i++){
			nth_element(p+i,p+i,p+n,cmp);
			printf(" %d",p[i].id);
			pos++;
		}
		putchar('\n');
	}
}

POJ 1039 Pipe

//https://blog.csdn.net/huayunhualuo/article/details/47971577
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double D;
const D eps=1e-8,inf=1e99;
int n,i,j,k,fl;
D mx;
struct P{
	D x,y;
	P(){};
	P(D xx,D yy){x=xx;y=yy;}
	friend P operator+(P p1,P p2){return P(p1.x+p2.x,p1.y+p2.y);}
	friend P operator-(P p1,P p2){return P(p1.x-p2.x,p1.y-p2.y);}
	friend P operator*(P p1,P p2){return P(p1.x*p2.x,p1.y*p2.y);}
	friend D operator^(P p1,P p2){return p1.x*p2.y-p2.x*p1.y;}
}up[22],dn[22];
int sgn(D x){
	if (fabs(x)<eps) return 0;
	if (x>0) return 1;
	return -1;
}
void get_line(P p1,P p2,D &a,D &b,D &c){a=p2.y-p1.y;b=p1.x-p2.x;c=-p1.x*a-p1.y*b;}
P get_inter(P p1,P p2,P p3,P p4){
	D a1,b1,c1,a2,b2,c2,d;
	get_line(p1,p2,a1,b1,c1);
	get_line(p3,p4,a2,b2,c2);
	P p5=P(-inf,-inf);
	if (sgn(a1)==0 && sgn(a2)==0 || sgn(b1)==0 && sgn(b2)==0) return p5;
	if (sgn(b1)!=0 && sgn(b2)!=0 && sgn(a1/b1-a2/b2)==0) return p5;
	d=a1*b2-a2*b1;
	p5=P((b1*c2-b2*c1)/d,(a2*c1-a1*c2)/d);
	return p5;
}
D dir(P p,P p1,P p2){return (p-p1)^(p-p2);}
D cal(P p1,P p2,P p3,P p4){
	P p5=get_inter(p1,p2,p3,p4);
	return p5.x;
}
int main(){
	while (~scanf("%d",&n) && n){
		for (i=1;i<=n;i++){
			scanf("%lf%lf",&up[i].x,&up[i].y);
			dn[i].x=up[i].x;
			dn[i].y=up[i].y-1;
		}
		fl=0;mx=-inf;
		for (i=1;i<=n && !fl;i++)
			for (j=1;j<=n;j++)
				if (i!=j){
					for (k=1;k<=n;k++)
						if (sgn(dir(up[i],dn[j],up[k])*dir(up[i],dn[j],dn[k]))>0) break;
					if (k>n){
						fl=1;
						break;
					}
					if (k>1) mx=max(mx,max(cal(up[i],dn[j],up[k],up[k-1]),cal(up[i],dn[j],dn[k],dn[k-1])));
				}
		if (fl) puts("Through all the pipe.");
		else printf("%.2f\n",mx);
	}
}

POJ 2074 Line of Sight

//https://blog.csdn.net/r1986799047/article/details/48235293有数据
//https://blog.csdn.net/f_cpp/article/details/40952709详细题解
//u=up,d=down
#include<cstdio>
#include<algorithm>
using namespace std;
typedef double D;
const D eps=1e-6;
struct node{
	D x1,x2;
}v[402];
D las,ans,v1,v2,y,x1,x2,dx1,dx2,dy,ux1,ux2,uy;
int n,i,vn;
bool cmp(node a,node b){
	return a.x1<b.x1;
}
D get(D x1,D x2,D y){
	return x1-(x2-x1)/(uy-y)*(y-dy);
}
int main(){
	while (~scanf("%lf%lf%lf",&ux1,&ux2,&uy) && ux1!=0 && ux2!=0){
		scanf("%lf%lf%lf%d",&dx1,&dx2,&dy,&n);
		vn=0;
		for (i=1;i<=n;i++){
			scanf("%lf%lf%lf",&x1,&x2,&y);
			if (y>=uy || y<=dy) continue;
			v1=get(x1,ux2,y);
			v2=get(x2,ux1,y);
			if (v2-dx1<eps || dx2-v1<eps) continue;
			v[++vn]=(node){max(v1,dx1),min(v2,dx2)};
		}
		sort(v+1,v+vn+1,cmp);
		ans=0;las=0;
		for (i=1;i<=vn;i++)
			if (v[i].x1>las) ans=max(ans,v[i].x1-las),las=v[i].x2;
			else las=max(las,v[i].x2);
		ans=max(ans,dx2-las);
		if (ans<eps) puts("No View");
		else printf("%.2f\n",ans);
	}
}