kadj squares(模拟).cpp

杭电acm解题报告2001---2099.

#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int n, len[110];
struct node {
	int sx,tx;
	int pre;
	int num;

	bool operator < (const node & t) const {
		return len[num] < len[ t.num ];
	}
}edge[110];

bool cal_point(int r1,int r2)
{
	int i,j;
	node now;
	int b1 = edge[r1].sx + 2*len[r1];
	int b2 = b1 + 4*len[r1];
	if(len[r2] <= len[r1]) {//r1 cover r2
		now.sx = b1 + 2*len[r2];
		if(2*len[r2] < len[r1]) {//cover compelete
			now.pre = r1;
		}
		else {//cover part
			now.pre = edge[r1].pre;
		}
	}
	else if(len[r2] <= 2*len[r1]) {//r2 cover r1
		now.sx = b1 + 2*(2*len[r1] - len[r2]) ;
		now.pre = edge[r1].pre;
	}
	else {
		if(edge[r1].pre != -1) {//r2 cover r1 compelete
			now.sx = b2 - 2*len[r2];
			int preb1 = edge[ edge[r1].pre ].sx + 2*len[ edge[r1].pre ];
			int pt = preb1 + 2*len[r2];//r1's cover in the same level with r2
			//careful to determine intersection
			if(edge[ edge[r1].pre ].tx > now.sx && pt > now.sx) {//r2 intersect with r1's cover
				return cal_point(edge[r1].pre, r2);
			}
			now.pre = edge[r1].pre;
		}
		else {//r1 had't cover, r2 is unlimit
			now.sx = b1 - 2*(len[r2] - 2*len[r1]);
			now.pre = -1;
		}
	}
	now.tx = now.sx + 4*len[r2];
	edge[r2] = now;
	return true;
}

int main()
{
	int i,j,ans;
	while(scanf("%d", &n)==1, n) {
		scanf("%d", &len[1]);
		edge[1].sx = 0;
		edge[1].tx = 4*len[1];
		edge[1].pre = -1;
		edge[1].num = 1;
		for(i=2;i<=n;i++) {
			scanf("%d", &len[i]);
			cal_point(i-1,i);
			edge[i].num = i;
		}

		int cover[13000];
		int left = INT_MAX, right = INT_MIN;
		memset(cover,-1,sizeof(cover));
		sort(edge, edge+n+1);
		for(i=1;i<=n;i++) {
			for(j=edge[i].sx;j<=edge[i].tx;j++) {
				cover[j+6000] = edge[i].num;
				left = min(left, j+6000);
				right = max(right, j+6000);
			}
		}

		int num[100];
		int pre = -1, ans = 0;
		for(i=left;i<=right;i++) {
			if(pre != cover[i]) {
				pre = cover[i];
				num[ans ++] = pre;
			}
		}
		sort(num,num+ans);
		printf("%d", num[0]);
		for(i=1;i<ans;i++) {
			printf(" %d", num[i]);
		}
		printf("\n");
	}
}