| ||||||||||
| 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