Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 线段树觉得很难。抄的。费了很大的力气才整明白。 但是MAX_N 220 WA, 改成500ac 。。。。很奇怪

Posted by 274856653 at 2019-08-29 13:48:00 on Problem 1151
```#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: