Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator