Polygons

C++ 解法, 执行用时: 738ms, 内存消耗: 118392K, 提交时间: 2022-06-18 19:40:07

/*
Author: fffasttime
Date: 2019/07/27 21:00
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inc(i,n) for (int i=0;i<n;i++)
const int N=1010;
typedef double db;
const db eps=1e-10;
bool eq(db x){return fabs(x)<eps;}
struct vec{
	db x,y;
	vec operator-(const vec &v)const{return {x-v.x,y-v.y};}
	vec operator+(const vec &v)const{return {x+v.x,y+v.y};}
	vec operator*(db t)const{return {x*t,y*t};}
	bool operator<(const vec &v) const{return eq(x-v.x)?y<v.y:x<v.x;}
	db operator&(const vec &v)const{return x*v.y-y*v.x;}
	void rd(){scanf("%lf%lf",&x,&y);}
	//void rd(){x=rand()%1000; y=rand()%1000;}
	db ang()const{return atan2(y,x);}
}p[N*N*2],l1[N],l2[N];//p[n..n+2q] used for question

const db pi=acos(-1);

struct Edge{ //main transfer structure
	db ang; int u,v,w; bool vis;
	int rk;
	int fr;
	Edge(){}
	Edge(int u, int v, int w):u(u),v(v){
		ang=(p[v]-p[u]).ang();
		rk=fr=0;
		vis=0;
	}
	bool operator<(const Edge &v)const{return ang<v.ang;}
}ed[N*N*4];
int edc=1,gcnt=0;

vector<int> ed1[N*N];
vector<int> linep[N];
db ans[N*N*2]; int ansc;
vec lineInt(vec p, vec vp, vec q, vec vq){
	db t=(vq & p-q)/(vp&vq);
	return p+vp*t;
}
int main(){
	int n0; scanf("%d",&n0);
	int n=0;
	inc(i,n0){
		l1[i].rd(); l2[i].rd();
		inc(j,i) if (!eq((l2[i]-l1[i]&l2[j]-l1[j]))){
			p[n]=lineInt(l1[i],l2[i]-l1[i],l1[j],l2[j]-l1[j]);
			linep[i].push_back(n);
			linep[j].push_back(n);
			n++;
		}
	}
	inc(i,n0){
		sort(linep[i].begin(),linep[i].end(),[&](int x, int y){return p[x]<p[y];});
		for (int j=0;j<linep[i].size()-1;j++){
			int x=linep[i][j], y=linep[i][j+1];
			ed[++edc]=Edge(x,y,0);
			ed1[x].push_back(edc);
			ed[++edc]=Edge(y,x,0);
			ed1[y].push_back(edc);
		}
	}
	inc(i,n){
		sort(ed1[i].begin(),ed1[i].end(),[&](int a, int b){return ed[a].ang<ed[b].ang;});
		inc(j,ed1[i].size())
			ed[ed1[i][j]].rk=j;
	}
	int gout;
	for (int i=2;i<=edc;i++) if(!ed[i].vis){ //new
		int u=ed[i].u; int cur=i;
		gcnt++;
		db area=0;
		while (!ed[cur].vis){ //face
			ed[cur].fr=gcnt;
			ed[cur].vis=1;
			area+=(p[ed[cur].u]-p[u])&(p[ed[cur].v]-p[u]);
			int sz=ed1[ed[cur].v].size();
			int rk1=(ed[cur^1].rk-1+sz)%sz;
			cur=ed1[ed[cur].v][rk1];
		}
		if (area<=0) gout=gcnt;
		else ans[ansc++]=area/2;
	}
	sort(ans,ans+ansc,greater<db>());
	printf("%d %.6f %.6f\n",ansc,ans[0],ans[ansc-1]);
	int q; scanf("%d",&q);
	while (q--){
		int t; scanf("%d",&t);t--;
		if (t>=ansc) puts("Invalid question");
		else printf("%.6f\n",ans[t]);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 993ms, 内存消耗: 114960K, 提交时间: 2019-07-21 18:00:23

#include <bits/stdc++.h>
#define pb push_back
const double eps=1e-8;
using namespace std;
vector<int>G[1005];
vector<double>S;
vector<int>E[1005*1005];
vector<bool>vis[1005*1005];
int n;
int sgn(double x){
	if(fabs(x)<eps)return 0;
	if(x<0)return -1;
	return 1;
}
struct Point{
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y){}
	double operator^(const Point& b)const{return x*b.y-y*b.x;}
	Point operator+(const Point& b)const{return Point(x+b.x,y+b.y);}
	Point operator-(const Point& b)const{return Point(x-b.x,y-b.y);}
}a[5205];
vector<Point>P;
bool cmp(int a,int b){
	if(sgn(P[a].x-P[b].x)==0)return P[a].y<P[b].y;
	return P[a].x<P[b].x;
}
Point cross(Point s1,Point e1,Point s2,Point e2){
	Point u=s1-s2,v=e1-s1,w=e2-s2;
	Point p;
	p.x=(w^u)/(v^w)*v.x+s1.x;
	p.y=(w^u)/(v^w)*v.y+s1.y;
	return p;
}
void build(){
	for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
		if(sgn((a[2*i]-a[2*i+1])^(a[2*j]-a[2*j+1]))==0)continue;
		P.pb(cross(a[2*i],a[2*i+1],a[2*j],a[2*j+1]));
		G[i].pb(P.size()-1);//i这条直线上有P[size()-1]这个点,标号 
		G[j].pb(P.size()-1);
	}
	for(int i=0;i<n;i++){
		sort(G[i].begin(),G[i].end(),cmp);
		for(int j=0;j<G[i].size()-1;j++){
			E[G[i][j]].pb(G[i][j+1]);
			E[G[i][j+1]].pb(G[i][j]);
		}
	}
	for(int i=0;i<P.size();i++)vis[i]=vector<bool>(E[i].size(),0);
}
int st;
vector<Point>tmp;
bool dfs(int u,int fa){
	tmp.pb(P[u]);
	if(u==st){
		double s=0.0;
		for(int i=0;i<tmp.size()-1;i++)s+=(tmp[i]^tmp[i+1]);
		s+=(tmp[tmp.size()-1]^tmp[0]); 
		S.pb(fabs(s)*0.5);
		return 1;
	}
	int Min=-1,num=-1;
	for(int i=0;i<E[u].size();i++){
		int v=E[u][i];
		if(v==fa||vis[u][i])continue;
		if(sgn((P[v]-P[u])^(P[u]-P[fa]))<0 && 
			(Min==-1||sgn((P[v]-P[u])^(P[Min]-P[u]))<0))Min=v,num=i;
	}
	if(Min==-1)return 0;
	if(dfs(Min,u)){
		vis[u][num]=1;
		return 1;
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lf%lf%lf%lf",&a[2*i].x,&a[2*i].y,&a[2*i+1].x,&a[2*i+1].y);
	
	build();//for(int i=0;i<P.size();i++)cout<<P[i].x<<" "<<P[i].y<<endl;
	for(int i=0;i<P.size();i++){
		st=i;
		for(int j=0;j<E[i].size();j++){
			if(vis[i][j]==0){
				tmp.clear();
				if(dfs(E[i][j],i))vis[i][j]=1;
			}
		}			
	}
	sort(S.begin(),S.end());
	reverse(S.begin(),S.end());
	printf("%d %.5lf %.5lf\n",S.size(),S[0],S[S.size()-1]);
	int x,q;
	scanf("%d",&q);
	while(q--){
		scanf("%d",&x);
		if(x>S.size())printf("Invalid question\n");
		else printf("%.5lf\n",S[x-1]);
	}
	return 0;
}

详情