Floods (想法题)

原题:Gym-101808E

题意:

有一个用n个点表示的山峰,问下雨的时候最多可以积多少的水

解析:

首先,我们应该可以想到,找出最高点,往次最高点延申

这里有两种做法

我们对于次最高点求出其往最高点平移是碰到的那个点,然后把从那个点开始到次最高点的所有点组合成一个多边形,用叉积求一下这个多边形的面积,就是水的面积了

struct point{F x,y;point(){}point(F x,F y):x(x),y(y){}
};
Point P[1005];
int n;
double PolygonArea(){double sum = 0;Point O = Point(0, 0);for (int i = 0; i < n; i++)sum += Cross(P[i] - O, P[(i + 1) % n] - O);if (sum < 0)sum = -sum;return sum / 2;
}

第二种方法比较简单,写起来简单一些,我们对第一种方法进行优化,在次最高点延申后不急于求水的面积,而是求,此最高点和最高点之间的山和水的面积和(要么是一个梯形,要么是一个矩形,要么是一个梯形加上矩形),最后减去山的面积就行(一个梯形)

代码:

D read(){ D ans=0; char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans; return ans;
}struct node{F x,y;int id;bool operator <(const node a)const{return y<a.y;}
}po;F x[100009],y[100009];int main(){int t=read();while(t--){int n=read();priority_queue<node>q;for(int i=1;i<=n;i++){scanf("%lf%lf",&po.x,&po.y);x[i]=po.x,y[i]=po.y;po.id=i;q.push(po);}int l=q.top().id,r=q.top().id;q.pop();F ans=0;while(!q.empty()){po=q.top();q.pop();if(po.id<=r&&po.id>=l)continue;int a,b;if(po.id<l)a=l,b=l-1;else a=r,b=r+1;if(y[po.id]==y[a])ans+=(y[a]+y[po.id])*abs(x[a]-x[po.id])/2.0;//相同高是矩形else if(po.id==b)ans+=(y[a]+y[b])*abs(x[a]-x[b])/2.0;//相邻是梯形else {//否则是一个梯形加一个矩形F K=(y[a]-y[b])/(x[a]-x[b]),B=y[a]-(y[a]-y[b])*x[a]/(x[a]-x[b]);F xx=(y[po.id]-B)/K;ans+=abs(xx-x[po.id])*y[po.id]+(y[po.id]+y[a])*abs(x[a]-xx)/2.0;}l=min(l,po.id),r=max(r,po.id);}for(int i=1;i<n;i++){ans-=abs(x[i]-x[i+1])*(y[i]+y[i+1])/2.0;}printf("%.8f\n",ans);}
}