首页 > ACM题库 > HDU-杭电 > HDU 4102-Books[解题报告]HOJ
2015
04-16

HDU 4102-Books[解题报告]HOJ

Books

问题描述 :

Ali and Baba

Ali’s room is full of books and he has never come up with a good way to arrange them. He just put them on the desk. But sometimes the books became unstable due to the gravity, and some might slide off the desk. He found it very annoying and decided to use a new method to put his books.
He bought some magic clips to stabilize the books. Once he put a book onto the desk, he will check if the book is steady. If it is, then he will use a clip to stabilize it and it will never slide or flip. If not, he will just pick up the book and throw it onto the floor and deal with it later.
But as he began to use the new method, he found it hard to decide whether a book is steady when put it on the desk. So he needs your help to determine that.
Assume that every book has the same thickness.
A book is steady means it will stay unmoved and horizontal even if given a small force.

输入:

The input consists several testcases.
The first line contains the number of books N (1 <= N <= 2000).
The following N lines each contains four integers, x1,y1,x2,y2 (-103 <= x1, y1, x2, y2 <= 103), means that the i-th book is placed with lower-left-corner placed at x1,y1 and upper-right-corner placed at x2,y2 (if you look down from above). The book’s edge is always paralleled with the desk’s edge.

输出:

The input consists several testcases.
The first line contains the number of books N (1 <= N <= 2000).
The following N lines each contains four integers, x1,y1,x2,y2 (-103 <= x1, y1, x2, y2 <= 103), means that the i-th book is placed with lower-left-corner placed at x1,y1 and upper-right-corner placed at x2,y2 (if you look down from above). The book’s edge is always paralleled with the desk’s edge.

样例输入:

3
0 0 2 2
-1 0 3 1
2 0 3 2

样例输出:

2

#include <stdio.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
#define N 8005
#define EPS 1e-8

struct TPoint {
	int x, y;
	TPoint() {
	}
	TPoint(const int &_x, const int &_y) :
		x(_x), y(_y) {
	}
	bool operator ==(const TPoint &b) const {
		return (x == b.x && y == b.y);
	}
	TPoint operator-(const TPoint &b) const {
		return TPoint(x - b.x, y - b.y);
	}
};

TPoint p[N], hull[N],r;
int tn;
double cross(const TPoint & a, const TPoint & b, const TPoint & c) {
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
double len(const TPoint &a) {
	return sqrt((double) (a.x * a.x + a.y * a.y));
}
double dis(const TPoint &a, const TPoint &b) {
	return len(b - a);
}
bool graham_cmp(const TPoint &b, const TPoint &c) {
	double tmp = cross(b, c, p[0]);
	if (tmp > EPS)
		return true;
	if (fabs(tmp) < EPS && (dis(b, p[0]) < dis(c, p[0])))
		return true;
	return false;
}
int graham_scan(int n) {
	int top, i, k = 0;
	for (i = 1; i < n; ++i) {
		if ((p[k].y - p[i].y < EPS) || (fabs((double)p[i].y - p[k].y) < EPS && p[k].x
				- p[i].x > EPS))
			k = i;
	}
	swap(p[0], p[k]);
	sort(p + 1, p + n, graham_cmp);
	hull[0] = p[0], hull[1] = p[1], hull[2] = p[2];
	if (n < 3)
		return n;
	else
		top = 3;
	for (i = 3; i < n; ++i) {
		while (top >= 2 && cross(hull[top - 2], hull[top - 1], p[i]) < EPS)
			--top;
		hull[top++] = p[i];
	}
	return top;
}
inline double dis_p2_line(TPoint & a,TPoint & b,TPoint & p)
{ return fabs(cross(a,p,b))/dis(a,b); }

struct node {
	int x1, x2, y1, y2;
	int level;
	bool flag;
} a[2005];
int Max(int a, int b) {
	return a > b ? a : b;
}
int Min(int a, int b) {
	return a < b ? a : b;
}
int main() {
	int i, j, n;
	int level, t, x, y;
	while (scanf("%d", &n) != EOF) {
		for (i = 0; i < n; ++i) {
			scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
			a[i].flag = false;
			a[i].x1 *= 2;
			a[i].y1 *= 2;
			a[i].x2 *= 2;
			a[i].y2 *= 2;
			if (a[i].x1 > a[i].x2) {
				t = a[i].x1;
				a[i].x1 = a[i].x2;
				a[i].x2 = t;
			}
			if (a[i].y1 > a[i].y2) {
				t = a[i].y1;
				a[i].y1 = a[i].y2;
				a[i].y2 = t;
			}
		}
		a[0].level = 1;
		a[0].flag = true;
		for (i = 1; i < n; ++i) {
			level = 1;
			for (j = i-1; j >= 0; --j) {
				if (level >= a[j].level + 1)
					continue;
				if (a[i].x2 <= a[j].x1)
					continue;
				if (a[j].x2 <= a[i].x1)
					continue;
				if (a[i].y2 <= a[j].y1)
					continue;
				if (a[j].y2 <= a[i].y1)
					continue;
				level = a[j].level + 1;
			}
			a[i].level = level;
			tn = 0;
			for (j = 0; j < i; ++j) {
				if (level != a[j].level + 1)
					continue;
				if (a[i].x2 <= a[j].x1)
					continue;
				if (a[j].x2 <= a[i].x1)
					continue;
				if (a[i].y2 <= a[j].y1)
					continue;
				if (a[j].y2 <= a[i].y1)
					continue;
				int x1,x2,y1,y2;
				x1 = Max(a[i].x1,a[j].x1);
				x2 = Min(a[i].x2,a[j].x2);
				y1 = Max(a[i].y1,a[j].y1);
				y2 = Min(a[i].y2,a[j].y2);
				p[tn].x = x1;
				p[tn++].y = y1;
				p[tn].x = x1;
				p[tn++].y = y2;
				p[tn].x = x2;
				p[tn++].y = y1;
				p[tn].x = x2;
				p[tn++].y = y2;
			}
			if(tn==0)
			{
				a[i].flag=true;
				continue;
			}
			p[tn].x=((a[i].x1+a[i].x2)>>1);
			p[tn++].y=((a[i].y1+a[i].y2)>>1);
			tn=graham_scan(tn);
			a[i].flag=true;
			for(j=0;j<tn;++j)
			{
				if(hull[j]==TPoint(((a[i].x1+a[i].x2)>>1),((a[i].y1+a[i].y2)>>1)))
				{
					a[i].flag=false;
					a[i].level=-1;
					break;
				}
				r=TPoint(((a[i].x1+a[i].x2)>>1),((a[i].y1+a[i].y2)>>1));
				double s=fabs(dis_p2_line(hull[j],hull[(j+1)%tn],r));
				if(s<EPS)
				{
					a[i].flag=false;
					a[i].level=-1;
					break;
				}
			}
		}
		int ans=0;
		for(i=0;i<n;++i)
		{
			if(a[i].flag)
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}