C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 404K, 提交时间: 2022-08-16 15:52:53

#include<iostream>
#include<vector>
#include<cmath>
#define _for(i,L,R) for(int i=L;i<=R;++i)
//#define int long long
       
using namespace std;

using pdd=pair<double,double>;
vector<pdd> a,b;
const double INF=1e8;
int n,m;
#define x first
#define y second

double area(const vector<pdd> &points)
{
    int point_num = points.size();
    if(point_num < 3) return 0.0;
    double s = 0;
    for(int i = 0; i < point_num; ++i)
        s += points[i].x * points[(i+1)%point_num].y - points[i].y * points[(i+1)%point_num].x;
    return fabs(s/2.0);
}

class Line{
public:
	pdd st,ed;
};

pdd operator-(const pdd &a,const pdd &b)
{
	return {a.x-b.x,a.y-b.y};
}

double cross(pdd a,pdd b)
{
	return a.x*b.y-a.y*b.x;
}

double Cross(pdd p1, pdd p2, pdd p0)
{
    return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

bool isColide(pdd p1,pdd p2,pdd p3,pdd p4)
{
    double tmp = Cross(p2, p3, p1)*Cross(p2, p4, p1);
    return tmp < 0.0 || fabs(tmp) < 1e-6;
}

pdd getPoint(pdd p1, pdd p2, pdd p3, pdd p4)
{
    double x1 = p1.x, y1 = p1.y;
    double x2 = p2.x, y2 = p2.y;
    double x3 = p3.x, y3 = p3.y;
    double x4 = p4.x, y4 = p4.y;
    double t = ((x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1)) / ((x2 - x1)*(y3 - y4) - (x3 - x4)*(y2 - y1));
    return pdd(x3 + t*(x4 - x3), y3 + t*(y4 - y3));
}


int main()
{
	scanf("%d",&n);
	double x,y;
	_for(i,1,n) scanf("%lf%lf",&x,&y),a.push_back({x,y});
	scanf("%d",&m);
	_for(i,1,m) scanf("%lf%lf",&x,&y),b.push_back({x,y});
	double res=0;
	_for(i,0,m-1){
		vector<pdd> v;
//		printf("--- (%.3lf , %.3lf)  (%.3lf , %.3lf)\n",b[i].x,b[i].y,b[(i+1)%m].x,b[(i+1)%m].y);
		_for(j,0,n-1){
			if(cross(a[j]-b[i],a[j]-b[(i+1)%m])<0) v.push_back(a[j]);
			if(isColide(b[i],b[(i+1)%m],a[j],a[(j+1)%n])){
				pdd tmp=getPoint(b[i],b[(i+1)%m],a[j],a[(j+1)%n]);
				v.push_back(tmp);
			}
		}
//		printf("--\n");
//		for(pdd tmp:v) printf("[%.3lf %.3lf]\n",tmp.x,tmp.y);
		res=max(res,area(v));
	}
	printf("%.6lf\n",res);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 456K, 提交时间: 2022-11-24 16:43:48

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;++i)
#define _rep(i,s,t) for(int i=s;i>=t;--i)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
typedef long long ll;
typedef double db;
const int N=81;
const db eps=1e-9;
int n,m;
db ans;
struct point{
	db x,y;
	point(db X=0.,db Y=0.){
		x=X,y=Y;
	}
	point operator+(point A)const{
		return point(x+A.x,y+A.y);
	}
	point operator-(point A)const{
		return point(x-A.x,y-A.y);
	}
	db operator*(point A)const{
		return x*A.y-y*A.x;
	}
	point operator*(db k)const{
		return point(k*x,k*y);
	}
	db operator^(point A)const{
		return x*A.x+y*A.y;
	}
	void in(){
		cin>>x>>y;
	}
	void out(){
		cout<<x<<" "<<y<<endl;
	}
}a[N],b[N];
vector<point>V;
db getS(){
	point p=*(V.begin());
	int sz=V.size()-1;
	db ans=0;
	rep(i,1,sz)
		ans+=(V[i]-p)*(V[i-1]-p);
	return fabs(ans);
}
int sgn(db x){
	if(x>eps)return 1;
	if(x<-eps)return -1;
	return 0;
}
bool across(point a,point b,point c,point d){
	return sgn((b-a)*(c-a))*sgn((b-a)*(d-a))<=0;
}
point g(point a,point b,point p,point q){
	db u=(p-a)*(q-p),d=(b-a)*(q-p);
	return a+(b-a)*(u/d);
}
int main(){
	cin>>n;
	rep(i,0,n-1)
		a[i].in();
	cin>>m;
	rep(i,0,m-1)
		b[i].in();
	rep(i,0,m-1){
		V.clear();
		rep(j,0,n-1){
			if((b[(i+1)%m]-b[i])*(a[j]-b[i])<0)
				V.pb(a[j]);
			if(across(b[(i+1)%m],b[i],a[(j+1)%n],a[j]))
				V.pb(g(b[(i+1)%m],b[i],a[(j+1)%n],a[j]));
		}
		ans=max(ans,getS());
	}
	printf("%.12lf\n",ans/2);
	return 0;
}