 /**//*
有一些多边形掉下来,要询问区间[A,B]内掉下来的多边形的面积

看解题报告的:
“我们过每一个出现的横坐标做和y轴平行的竖直线,那么天上掉下
来的多边形就被切割成一个一个的梯形(三角形可以看做是特殊的
梯形),因此这个问题可以简化为掉下梯形的情况。试想,在一个
区间如果掉下的不是梯形,而是数字,然后查询的是求区间掉下
的数字的和,这样的问题该怎么做?”

这里用树状数组做

之前用double写的wa,不知哪里的问题,题目说都是int 改用int才过

对所有点离散化先,然后对每个询问
Q的话就输出区间和
R的话就竖直线切割,并插入面积到树状数组里
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<cassert>

using namespace std;

const int INF = 1000000010;
const int MAXN = 25010;

struct Point
  {
int x, y;
void read()
 {
scanf("%d%d",&x , &y);
}
};

struct Polygon
  {
int n;
Point pt[10];
void read()
 {
scanf("%d",&n);
for(int i = 0 ; i < n; i++)
pt[i].read();
}
int xMin()
 {
int ans = INF;
for(int i = 0 ; i < n ; i++)
ans = min(ans , pt[i].x);
return ans;
}
int xMax()
 {
int ans = -INF;
for(int i = 0 ; i < n ; i++)
ans = max(ans , pt[i].x);
return ans;
}
};

Polygon polygon[MAXN];


struct OP
  {
char ch;
int A , B;
 OP() {}
};

OP op[MAXN];
int N;
double C[MAXN*10];


void init()
  {
for(int i = 0 ; i <= N; i++)
C[i] = 0.0;
}
int lowbit(int x)
  {
return x & (-x);
}

void insert(int p , double x)
  {
while(p<=N)
 {
C[p] += x;
p += lowbit(p);
}
}

double sum(int p)
  {
double ans = 0;
while(p>0)
 {
ans += C[p];
p -= lowbit(p);
}
return ans;
}

double cal(double x , Point a , Point b)
  {
return a.y - (a.x-x)*(a.y-b.y)/(a.x-b.x);
}


#define Xfind(x) (lower_bound(X.begin() , X.end() , (x) ) - X.begin())

int main()
  {

#ifdef ONLINE_JUDGE
#else
freopen("in", "r", stdin);
#endif

int T , Q;
for(scanf("%d",&T) ; T--; )
 {
vector<int> X;
scanf("%d",&Q);
for(int i = 0 ; i < Q ; i++)
 {
scanf(" %c" , &op[i].ch);
if(op[i].ch == 'R')
 {
polygon[i].read();
for(int j = 0 ; j < polygon[i].n ; j++)
 {
X.push_back(polygon[i].pt[j].x);
}
}
else
 {
scanf("%d %d",&op[i].A , &op[i].B);
X.push_back(op[i].A);
X.push_back(op[i].B);
}
}

X.push_back(0);
X.push_back(INF);
sort(X.begin() , X.end());
X.erase(unique(X.begin() , X.end()) , X.end() );
N =X.size();
init();

for(int i = 0 ; i < Q ; i++)
 {
if(op[i].ch == 'Q')
 {
int low = Xfind(op[i].A);
int high = Xfind(op[i].B);
printf("%.3f\n" , sum(high) - sum(low) );
}
else
 {
Polygon poly = polygon[i];
int left = poly.xMin();
int right = poly.xMax();
left = Xfind(left);
right = Xfind(right);
double last;
int n = poly.n;
for(int j = left ; j <= right ; j++)
 {
vector<int> vt;
for(int ii = 0 ; ii < n ; ii++)
 {
int low = Xfind(poly.pt[ii].x);
int high = Xfind(poly.pt[(ii+1)%n].x);
if(low > high)swap(low,high);
if(low <= j && j <= high)vt.push_back(ii);
}
assert(vt.size() >= 2);
if(vt.size() == 3)
 {
if(poly.pt[vt[0]].x == X[j])vt.erase(vt.begin());
else if(poly.pt[vt[1]].x == X[j])vt.erase(vt.begin()+1);
else if(poly.pt[vt[2]].x == X[j])vt.erase(vt.begin()+2);
}
double y1 = cal(X[j] , poly.pt[vt[0]] , poly.pt[(vt[0]+1)%n]);
double y2 = cal(X[j] , poly.pt[vt[1]] , poly.pt[(vt[1]+1)%n]);
if(y1 > y2)swap(y1,y2);
 if( j == left ) {last = y2 - y1; continue;}
double ans = (last + y2 - y1)*(X[j] - X[j-1])/2;
last = y2 - y1;
insert(j,ans);
}
}
}
}
return 0;
}


|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|