/**//* 有一些多边形掉下来,要询问区间[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
搜索
最新评论
|
|