2014
02-24

# Bricks

You have some equal-height bricks and want to pile them into a two-layered object. To ensure the stability of the object, no full half-blocks can be over empty space. There are totally four half-blocks for each brick, shown below.

The following figure shows an object consisting of four 2 * 2 * h bricks in the lower layer, one 2 * 2 * h brick in the upper layer. Each half-block does not include its boundary, so you’re not allowed to leave only one brick, since the upper brick would have two half-blocks hanging over empty space (though you may argue that the upper brick may stand still if you don’t touch it). In this case, at most 2 bricks could be removed.

Each time, you can remove exactly one brick from the lower layer by dragging it in one of four possible directions: decreasing x (left), increasing x (right), decreasing y (front), increasing y (back). You can only drag a brick along one direction. E.g. you cannot drag it to the left, and then to the front to remove it. The bricks are smooth enough and don’t suffer from fraction, so you can remove any brick you want as long as dragging it out does not hit any other brick (touching other bricks is allowed, though), and after the brick is removed, no full half-blocks of any brick in upper layer are over empty space.

Write a program to find the maximum number of bricks you can remove from the lower layer.

The input contains several test cases. The first line of input contains two integer m, n (1<=m, n<=10) , the number of bricks in the lower and upper layer. The next line describes the lower layer with m brick descriptions in format (x1, y1) – (x2, y2) where integers x1, y1, x2, y2 do not exceed 1000 by their absolute values and they satisfy x1 < x2, y1 < y2 . Each description does not contain any space inside; neighboring descriptions are separated by exactly one single space. The next line describes the upper layer in the same format. The initial object is always valid. The last test case is followed by a single zero, which should not be processed.

The input contains several test cases. The first line of input contains two integer m, n (1<=m, n<=10) , the number of bricks in the lower and upper layer. The next line describes the lower layer with m brick descriptions in format (x1, y1) – (x2, y2) where integers x1, y1, x2, y2 do not exceed 1000 by their absolute values and they satisfy x1 < x2, y1 < y2 . Each description does not contain any space inside; neighboring descriptions are separated by exactly one single space. The next line describes the upper layer in the same format. The initial object is always valid. The last test case is followed by a single zero, which should not be processed.

1 1
(0,0)-(1,1)
(0,0)-(1,1)
4 1
(0,0)-(2,2) (2,0)-(4,2) (0,2)-(2,4) (2,2)-(4,4)
(1,1)-(3,3)
0

Case 1: 0
Case 2: 2

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
double a, b, c, d, e, EPS = 1e-8;
int sign(double x)
{
return x < -EPS ? -1 : (x > EPS ? 1 : 0);
}
bool top(double x)
{
double co = x / a;
double si = sqrt(1 - co * co);
double h = co * b + sqrt(a * a - x * x);
return sign(h - d) <= 0;
}
bool right(double x)
{
double co = x / a;
double si = sqrt(1 - co * co);
double r = b * si + x;
return sign(r - e) <= 0;
}

bool check()
{
double l = 0, r = a;
if (sign(a - e) > 0) return false;
for (int i = 0; i < 200; ++i)
{
double mid = (l + r) / 2;
// cout << mid << endl;
if (!top(mid)) r = mid;
else if (!right(mid)) l = mid;
else return true;
}
return false;
}
int main()
{
while (cin >> a >> b >> c >> d >> e)
{
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
if (d > e) swap(d, e);
// cout << a << " "<<b << " " <<d << " " << e << endl;
puts(check() ? "YES" : "NO");
}
return 0;
}

1. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

2. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

3. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1