题意:问n条直线交出来的所有多边形的面积。
最左转线法求平面区域的模板题。在WC2013平面图前就是个弟弟。
/*
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;
}