90pts求助...
查看原帖
90pts求助...
119725
皓月当蓝空楼主2022/7/31 23:16

wa最后一个点,且与答案差别在小数点后第二位qaq

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define re register int 
#define in inline
#define eps 1e-8
#define maxn 500005
using namespace std;

in int read()
{
	int ans=0,f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) ans=ans*10+ch-'0';
	return ans*f;
}

struct Point{
	double x,y;
	Point(double x,double y){
		this->x=x;
		this->y=y;
	}
	in double Length(){
		return sqrt(x*x+y*y);
	}
	Point(){};
}p[maxn],bao[maxn*2];
int en;
const double pi=acos(-1.0);

typedef Point Vector;

int dcmp(double x)
{
	return fabs(x)<eps?0:(x<0?-1:1);
}
in bool operator ==(Point a,Point b)
{
	if(dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0) return 1;
	return 0;
}
in Vector operator +(Vector a,Vector b)
{
	return Vector(a.x+b.x,a.y+b.y);
}
in Vector operator -(Vector a,Vector b)
{
	return Vector(a.x-b.x,a.y-b.y);
}
in Vector operator *(Vector a,double b)
{
	return Vector(a.x*b,a.y*b);
}
in Vector Unit(Vector a)
{
	return a*(1/a.Length());
}
in double dot(Vector a,Vector b)
{
	return a.x*b.x+a.y*b.y;
}
in double cross(Vector a,Vector b)//如果 a 在 b 的左侧 那么a 在b 的右侧 
{
	return a.x*b.y-a.y*b.x;
}
in Vector rotate(Vector a,double rad)//向量逆时针旋转 rad 弧度 
{
	return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
in Point banana(Point p,Vector v,Point q,Vector w)//交点 
{
	return p+v*(cross(w,p-q)/cross(v,w));
}

in double DisToLine(Point p,Point a,Point b)//直线上两点 a,b 直线外一点 p	
{
	Vector v1=b-a,v2=p-a;
	return fabs(cross(v1,v2))/v1.Length();
}
in double DisToSegment(Point p,Point a,Point b)//线段 a,b 外一点 到ab 的距离 
{
	Vector v1=b-a,v2=p-a,v3=p-b;
	if(dot(v1,v2)<eps) return v2.Length();
	if(dot(v1,v3)>eps) return v3.Length();
	return fabs(cross(v1,v2))/v1.Length();
}
in Point GetLineProjection(Point p,Point a,Point b)//点 p 在 ab直线上的投影 
{
	Vector v=b-a;
	return a+v*(dot(v,p-a)/dot(v,v));
}


in bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)//规范相交 
{
	double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
	double c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
	return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool OnSegment(Point p,Point a1,Point a2)//一个点是否在线段上 
{
	if(p==a1||p==a2) return 1;
	return fabs(cross(a1-p,a2-p))<eps&&dot(a1-p,a2-p)<-eps;
}
in double polyonarea(Point p[],int n)//多边形的面积 
{
	double area=0;
	for(int i=1;i<n-1;i++) area+=cross(p[i]-p[0],p[i+1]-p[0]);
	return area/2.0;
}

in bool cmp(const Point & a,const Point & b)
{
	if(a.x!=b.x) return a.x<b.x;
	return a.y<b.y;
}
in double dis(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
in void tubao()//凸包 上下凸壳 
{
	int n;
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	en=0;
	sort(p+1,p+1+n,cmp);
	for(i=1;i<=n;i++){
		while(en>1&&cross(bao[en]-bao[en-1],p[i]-bao[en])<=0) en--;
		bao[++en]=p[i];
	}
	int half=en;
	for(i=n-1;i;i--){
		while(en>half&&cross(bao[en]-bao[en-1],p[i]-bao[en])<=0) en--;
		bao[++en]=p[i];
	}
	en--;
	double ans=0;
	for(i=2;i<=en;i++) ans+=dis(bao[i],bao[i-1]);
	printf("%.2lf\n",ans+dis(bao[1],bao[en]));
} 
in int quare(Vector a)
{
	if(a.x>0&&a.y>=0) return 1;
	if(a.x<=0&&a.y>0) return 2;
	if(a.x<0&&a.y<=0) return 3;
	if(a.x>=0&&a.y<0) return 4;
} 
bool operator <(Vector a,Vector b)
{
	if(quare(a)!=quare(b))
		return quare(a)<quare(b);
	return cross(a,b)>0;
}

bool same_dir(Vector a,Vector b)
{
	return (quare(a)==quare(b))&&(dcmp(cross(a,b))==0);
}
struct Line{
	Point p;
	Vector v;
	double ang;
	Line(){}
	Line(const Point &a,const Point &b){
		v=b-a;
		p=a;
		ang=atan2(v.y,v.x);//向量的极角 纵在前 横在后
		if(ang<0) ang+=2.0*pi; 
	}
}a[maxn];
in Point banana(Line x,Line y)//交点 
{
	return banana(x.p,x.v,y.p,y.v);
}
bool operator <(Line x,Line y)
{
	//return x.v<y.v;
	if(quare(x.v)==quare(y.v)&&fabs(cross(x.v,y.v))<eps) return cross(x.v,x.p+x.v-y.p)>0;
	else return x.v<y.v; 
}
Point b[maxn],c[maxn];
int n,tot,cnt,num;

Line dui[maxn];
int front,rear;
in int PointPostoLine(Point x,Line y)
{
	return cross(y.v,x-y.p);
}

in double f(double x)//待求函数 
{
	return -x;
}
in double area(double l,double r)
{
	return (r-l)/6.0*(f(l)+4.0*f((l+r)/2.0)+f(r));
}
in double sinp(double l,double r)//自适应辛普森积分法 
{
	double m=(l+r)*0.5;
	double t2=area(l,r),t3=area(l,m)+area(m,r);
	if(fabs(t2-t3)<eps) return t2;
	return sinp(l,m)+sinp(m,r);	
}
in Point getcircle(Point i,Point j,Point k)
{
	double a,b,c,d,e,f;
	a=i.x-j.x;
	b=i.y-j.y;
	c=i.x-j.x;
	d=i.y-j.y;
	e=((i.x*i.x-j.x*j.x)-(j.y*j.y-i.y*i.y))/2;
	f=((i.x*i.x-k.x*k.x)-(k.y*k.y-i.y*i.y))/2;
	Point as;
	as.x=-(d*e-b*f)/(b*c-a*d);
	as.y=-(a*f-c*e)/(b*c-a*d);
	return as;
}

int main()
{
	n=read();
	re i,j;
	int m;
	for(i=1;i<=n;i++){
		m=read();
		for(j=1;j<=m;j++){
			b[j].x=read(),b[j].y=read();
		}
		for(j=1;j<m;j++){
			a[++cnt].p=b[j];
			a[cnt].v=b[j+1]-b[j];
		}
		a[++cnt].p=b[m];
		a[cnt].v=b[1]-b[m];
	}
	sort(a+1,a+1+cnt);
	front=1,rear=0;
	for(i=1;i<=cnt;i++){
		while(front<rear&&PointPostoLine(banana(dui[rear],dui[rear-1]),a[i])<0) rear--;
		while(front<rear&&PointPostoLine(banana(dui[front],dui[front+1]),a[i])<0) front++;
		dui[++rear]=a[i];
	}
	while(front<rear&&PointPostoLine(banana(dui[rear],dui[rear-1]),dui[front])<0) rear--;
	while(front<rear&&PointPostoLine(banana(dui[front],dui[front+1]),dui[rear])<0) front++;
	if(rear-front<=1){
		printf("0.000");
		return 0;
	}
	for(i=front;i<rear;i++){
		c[num++]=banana(dui[i],dui[i+1]);
	}
	if(!(banana(dui[rear],dui[front])==c[0]))
		c[num++]=banana(dui[rear],dui[front]);
	printf("%.3lf\n",polyonarea(c,num));
	return 0;
}
/*
2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0

2
3
0 0 
2 0 
0 3
4
1 1 
3 1 
3 3 
1 3
*/

2022/7/31 23:16
加载中...