Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
线段树觉得很难。抄的。费了很大的力气才整明白。 但是MAX_N 220 WA, 改成500ac 。。。。很奇怪#include <stdio.h> #include <string.h> #include <iostream> #include<vector> #include<cstdio> #include<string> #include<algorithm> #include<queue> #define MAX_N 500 #define lson l, m, rt<<1 #define rson m+1,r, rt<<1|1 using namespace std; int n; typedef struct { double X1; double X2; double Y; int iFlag; }ST_Edge; ST_Edge stEdge[MAX_N]; double X[MAX_N]; typedef struct { int cnt; double len; }ST_Node; ST_Node stNode[MAX_N<<1]; void initVar() { memset((char *)&stEdge, 0, sizeof(stEdge)); memset((char *)&X, 0, sizeof(X)); memset((char *)&stNode, 0, sizeof(stNode)); } int cmpDouble(const void * a, const void * b) { return((*(double*)a-*(double*)b>0)?1:-1); } int cmpEdge(const void *p,const void *q){ ST_Edge* a = (ST_Edge *)p; ST_Edge* b = (ST_Edge *)q; return ((a->Y - b->Y)>0?1:-1); } void pushdown(int l, int r, int rt) { if(stNode[rt].cnt) { stNode[rt].len = X[r+1] - X[l]; // printf(" cnt rt = %d, l = %d, r = %d, stNode[rt].len = %f\n ", rt, l, r, stNode[rt].len); }else if(l == r) { stNode[rt].len = 0; // printf(" delete rt = %d, l = %d, r = %d, stNode[rt].len = %f\n ", rt, l, r, stNode[rt].len); }else { stNode[rt].len = stNode[rt<<1].len + stNode[rt<<1|1].len; // printf(" merge rt = %d, l = %d, r = %d, stNode[rt].len = %f, stNode[%d].len = %f, stNode[%d].len = %f\n ", rt, l, r, stNode[rt].len, rt<<1, stNode[rt<<1].len, rt<<1|1, stNode[rt<<1|1].len); } } void update(int L, int R, int l, int r, int rt, int val ) { //printf("update L = %d, R = %d, l = %d, r = %d, rt = %d, val = %d\n", L, R, l, r, rt, val); if(L<=l && r <= R) { stNode[rt].cnt += val; // printf("xiangxia gengxin, rt = %d, L = %d, R = %d, l = %d, r = %d, stNode[rt].cnt = %d\n", rt, L, R, l, r, stNode[rt].cnt); pushdown(l, r, rt ); return; } int m = (l + r)/2; if(L<=m) { // printf("left L = %d, R = %d, l = %d, r = %d, rt = %d, val = %d, m = %d\n", L, R, l, r, rt, val, m); update(L, R, lson, val ); } if(R>m) { // printf("right L = %d, R = %d, l = %d, r = %d, rt = %d, val = %d, m = %d\n", L, R, l, r, rt, val, m); update(L, R, rson, val ); } pushdown(l, r, rt); } int main() { double X1,Y1, X2,Y2; int iTestNum = 1; int i; while( scanf("%d", &n) != EOF ) { // printf("n = %d\n", n); if(0 == n) break; initVar(); for(i = 0; i<n; i++) { scanf("%lf %lf %lf %lf", &X1, &Y1, &X2, &Y2 ); // printf("X1 = %0.2f, Y1 = %0.2f, X2 = %0.2f, Y2 = %0.2f\n", X1, Y1, X2, Y2); stEdge[2*i].X1 = X1; stEdge[2*i].X2 = X2; stEdge[2*i].Y = Y1; stEdge[2*i].iFlag = 1; X[2*i] = X1; stEdge[2*i + 1].X1 = X1; stEdge[2*i + 1].X2 = X2; stEdge[2*i + 1].Y = Y2; stEdge[2*i + 1].iFlag = -1; X[2*i + 1] = X2; } qsort(X, 2*n,sizeof(double), cmpDouble ); // for(i = 0; i<2*n; i++) // { // printf("i = %d, X[i] = %f\n", i, X[i]); // } qsort(stEdge, 2*n, sizeof(ST_Edge), cmpEdge); // for(i = 0; i<2*n; i++) // { // printf("i = %d, stEdge[i].X1 = %f, stEdge[i].X2 = %f, stEdge[i].Y = %f, stEdge[i].iFlag = %d\n", i, stEdge[i].X1, stEdge[i].X2, stEdge[i].Y, stEdge[i].iFlag); // } int m=unique(X,X+2*n)-X; // printf("m = %d\n", m); double Ans = 0; for(i = 0; i<2*n; i++) { int l = lower_bound(X,X+m,stEdge[i].X1)-X; int r = lower_bound(X,X+m,stEdge[i].X2)-X -1; // printf("main i = %d, l = %d, r = %d, stEdge[i].iFlag = %d\n", i, l, r, stEdge[i].iFlag); update(l, r, 0, m, 1, stEdge[i].iFlag); Ans = Ans + (stNode[1].len * (stEdge[i+1].Y - stEdge[i].Y)); // printf("Ans i = %d, Ans = %0.2f , stNode[1].len = %0.2f, stEdge[i+1].Y - stEdge[i].Y = %0.2f \n", i, Ans, stNode[1].len, stEdge[i+1].Y - stEdge[i].Y); } printf("Test case #%d\n", iTestNum++); printf("Total explored area: %.2f\n\n", Ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator