首页 > ACM题库 > HDU-杭电 > HDU 3340-Rain in ACStar-计算几何-[解题报告]HOJ
2014
03-16

HDU 3340-Rain in ACStar-计算几何-[解题报告]HOJ

Rain in ACStar

问题描述 :

Maybe you have heard of Super Cow AC who is the great general of ACM Empire. However, do you know where he is from?
This is one of the ten biggest secrets of this world! And it is time to expose the truth!
Yes, Super Cow AC is from ACStar which is ten million light-year away from our earth. No one, even AC himself, knows how AC came to our home. The only memory in his head is the strange rain in ACStar.
Because of the special gravity of ACStar, the raindrops in ACStar have many funny features. They have arbitrary sizes, color and tastes. The most interesting parts of the raindrops are their shapes. When AC was very young, he found that all the drops he saw in air were convex hull. Once the raindrops fell to the ground, they would be absorb by the soil.
In Action
This year is set to be AC-year. In recognition of Great General AC’s contribution to our empire, the Emperor decided to build a huge AC park. Inside this park there is a laboratory to simulate the rain in ACStar. As a researcher of this lab, you are appointed to measure the volume of rain absorbed by soil. To simplify this problem, scientists put the rain into two-dimensional plane in which the ground is represented as a straight line and the raindrops are convex polygon. So the area of the graphics stands for the volume of raindrops.
You will receive two types of instructions:
1.R P (This type of instructions tell you sufficient information about the raindrops.)
2.Q A B (Ask you to report the volume of rain absorbed by soil of [A,B].)
Instructions are given in chronological order.

输入:

The first line of the inputs is T(no more than 10), which stands for the number of test cases you need to solve.
After T, the inputs will be each test case. The first line of each case will be N(no more than 25000), representing for the numbers of instructions. The following N lines will give instructions of the two types.
For each instruction of type 1, it will be followed by a line listing P (at least 3 and at most 5) points representing the convex polygon of the coming raindrop. The points are started by the leftmost point and are given in counterclockwise order. It’s guaranteed that no points of the same raindrop are in the same vertical line.
All numbers are positive integer no more than 1000000000.

输出:

The first line of the inputs is T(no more than 10), which stands for the number of test cases you need to solve.
After T, the inputs will be each test case. The first line of each case will be N(no more than 25000), representing for the numbers of instructions. The following N lines will give instructions of the two types.
For each instruction of type 1, it will be followed by a line listing P (at least 3 and at most 5) points representing the convex polygon of the coming raindrop. The points are started by the leftmost point and are given in counterclockwise order. It’s guaranteed that no points of the same raindrop are in the same vertical line.
All numbers are positive integer no more than 1000000000.

样例输入:

1
7
Q 1 100
R 4
10 10 11 10 13 11 12 11
Q 10 11
Q 1 100
R 3
100 20 120 20 110 30
Q 1 100
Q 12 120

样例输出:

0.000
0.250
1.000
1.000
100.250

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3340

题目大意:天下会掉下一些图形(三边形,四边形,五边形)在数轴上,求数轴上某一段区间落下的图形的面积和.

思路:
换了一种新写法,把初始化和算法部分分别写成init()函数和sof()函数,为什么要这样写呢?因为查错的时候相对会比较方便,也能相对提高代码的可读性.ok! 进入正题.
(1)数据比较大,很容易想到数据离散化,询问的区间是x,显然对x离散.
(2)又要更新(区间)又要询问,很容易就想到用线段树.
(3)那么线段树拿来干么?自然是用来统计面积和,直接统计面积肯定是不行的,因为图形的放置是随意的,所以我们可以根据每一条边的位置来间接求面积,我们按照点给出的顺序把边加到线段树中没加一条边,就算出该边和数轴构成的面积,根据下图我们可以知道图形的面积就等于绿色阴影部分减去黑色阴影部分,所以我们添加正边时(左端点的x小于右端点的),添加负面积,添加负边时(左端点的x大于右端点的),添加正面积,这样就可以把图形的面积加到树中,而且最多只有5条边,所以每次最多也只会进行5次的logn操作,所以整体的时间复杂度也只是O(nlogn)的.
Rain in ACStar
(4)更新时如何确定某段区间的左边高度和右边高度呢?因为通过上图我们可以知道,我们每添加一条边相对于添加一个梯形的面积进线段树(三角形可以看成上底为0的梯形),这样就很容易计算出某区间的左边高度和右边高度了,怎么计算,写写式子画画图弄一下就知道了.

代码:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ull unsigned __int64
#define ll __int64
//#define ull unsigned long long
//#define ll long long
#define son1 New(p.xl,xm,p.yl,ym),(rt<<2)-2
#define son2 New(p.xl,xm,min(ym+1,p.yr),p.yr),(rt<<2)-1
#define son3 New(min(xm+1,p.xr),p.xr,p.yl,ym),rt<<2
#define son4 New(min(xm+1,p.xr),p.xr,min(ym+1,p.yr),p.yr),rt<<2|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define middle (l+r)>>1
#define MOD 1000000007
#define esp (1e-8)
const int INF=0x3F3F3F3F;
const double DINF=10000.00;
//const double pi=acos(-1.0);
const int N=25010,M=150010;
int n,m,tot;
struct node{
	char op[2];
	int p,x[6],y[6];
}q[N];
int X[M],len[M<<2];
double vol[M<<2],ld[M<<2],rd[M<<2],tmp;

int bs(int key,int size,int A[]){
	int l=0,r=size-1,mid;
	while(l<=r){
		mid=middle;
		if(key>A[mid]) l=mid+1;
		else if(key<A[mid]) r=mid-1;
		else return mid;
	}return -1;
}

void init(){
	int i,j;
	scanf("%d",&n);
	for(i=m=0;i<n;i++){
		scanf("%s",q[i].op);
		if(q[i].op[0]=='Q'){
			scanf("%d%d",&q[i].x[0],&q[i].y[0]);
			X[m++]=q[i].x[0],X[m++]=q[i].y[0];
		}else{
			scanf("%d",&q[i].p);
			for(j=0;j<q[i].p;j++){
				scanf("%d%d",&q[i].x[j],&q[i].y[j]);
				X[m++]=q[i].x[j];
			}q[i].x[j]=q[i].x[0],q[i].y[j]=q[i].y[0];
		}
	}
	sort(X,X+m);
	for(i=tot=1;i<m;i++) if(X[i]!=X[i-1]) X[tot++]=X[i];
}

void Build(int l,int r,int rt){
	len[rt]=X[r+1]-X[l];
	vol[rt]=ld[rt]=rd[rt]=0;
	if(l==r) return;
	int mid=middle;
	Build(lson),Build(rson);
}

double Cal(double lc,double rc,int a,int b){return (rc*a+lc*b)/(a+b);}

void Func(int rt,double lc,double rc){
	ld[rt]+=lc,rd[rt]+=rc;
	vol[rt]+=(lc+rc)/2*len[rt];
}

void PushUp(int rt){vol[rt]=vol[rt<<1]+vol[rt<<1|1];}

void PushDown(int rt){
	if(ld[rt]==0 && rd[rt]==0) return;
	int ls=rt<<1,rs=ls|1;
	tmp=Cal(ld[rt],rd[rt],len[ls],len[rs]);
	Func(ls,ld[rt],tmp),Func(rs,tmp,rd[rt]);
	ld[rt]=rd[rt]=0;
}

void Update(int l,int r,int rt,int L,int R,double lc,double rc){
	if(L<=l && r<=R){
		Func(rt,Cal(lc,rc,X[l]-X[L],X[R+1]-X[l]),Cal(lc,rc,X[r+1]-X[L],X[R+1]-X[r+1]));
		return;
	}
	PushDown(rt);
	int mid=middle;
	if(L<=mid) Update(lson,L,R,lc,rc);
	if(mid<R) Update(rson,L,R,lc,rc);
	PushUp(rt);
}

double Query(int l,int r,int rt,int L,int R){
	if(L<=l && r<=R) return vol[rt];
	PushDown(rt);
	int mid=middle;
	double ret=0;
	if(L<=mid) ret+=Query(lson,L,R);
	if(mid<R) ret+=Query(rson,L,R);
	return ret;
}

void sof(){
	Build(0,tot,1);
	int i,j,l,r;
	for(i=0;i<n;i++){
		if(q[i].op[0]=='Q'){
			l=bs(q[i].x[0],tot,X),r=bs(q[i].y[0],tot,X);
			printf("%.3lf\n",l<r? Query(0,tot,1,l,r-1):0);
		}else for(j=0;j<q[i].p;j++){
			l=bs(q[i].x[j],tot,X),r=bs(q[i].x[j+1],tot,X);
			if(l<r) Update(0,tot,1,l,r-1,-q[i].y[j],-q[i].y[j+1]);
			else Update(0,tot,1,r,l-1,q[i].y[j+1],q[i].y[j]);
		}
	}
}

int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int T,cas;scanf("%d",&T);for(cas=1;cas<=T;cas++){
		init();
		sof();
	}
	return 0;
}

参考:http://blog.csdn.net/gotoac/article/details/7588254


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。