• [1031] Colorful Decoration

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述

  • You are going to decorate a very large white board with square sheets of colored paper. Each sheet of paper can be of any non-zero size. You have chosen N colors, numbered 0 to N - 1, and you will use exactly one sheet of each color. You are given four vector s, xa, ya, xb, and yb, each containing exactly N elements. The sheet of paper with color i must be placed so that its center is at either (xa[i], ya[i]) or (xb[i], yb[i]). All sides of the paper must be parallel to the coordinate axes, and no two sheets of paper can overlap each other (Two squares overlap if their intersection has a non-zero area). Return the maximum possible size of the smallest of the N sheets of paper. The size of a square sheet of paper is its side length. If you cannot place all N sheets, then return 0 instead.


    ↑this picture is for hint

  • 输入
  • Mutiple test cases.
    Each test is a line in the form of{xa, ya, xb, yb} where xa, ya, xb, yb is in the form
    of {a0, a1, a2, a3, ... an-1}.More details are referenced to the sample input.
    -xa will contain between 2 and 50 elements, inclusive.
    -xa, ya, xb, and yb will contain the same number of elements.
    -Each element of xa, ya, xb, and yb will be between 0 and 1,000,000,000, inclusive.
  • 输出
  • For each test case, output the answer in a single line.
  • 样例输入
  • {{10, 0, 7}, {0, 19, 6}, {20, 10, 25}, {20, 35, 25}}
{{464, 20}, {464, 10}, {464, 3}, {464, 16}}
{{0, 0, 1, 1}, {0, 0, 1, 1}, {1, 1, 0, 0}, {1, 1, 0, 0}}
{{0, 3, 0, 5, 6}, {1, 6, 0, 8, 5}, {6, 1, 7, 4, 7}, {5, 9, 2, 8, 9}}
{{1000000000, 0}, {0, 1000000000}, {0, 1000000000}, {0, 1000000000}}
  • 样例输出
  • 19
461
0
3
1000000000
  • 提示
  • In the picture above, the numbers represent the candidates for the center of each color. 
Choose (10, 0) for color 0, (0, 19) for color 1, and (25, 25) for color 2. The paper with
color 2 could be larger, but the size of the smallest sheet cannot exceed 19.
For the second test case:
(xa[i], ya[i]) and (xb[i], yb[i]) might be the same.
For the third test case:
No matter how we choose to place the squares, at least two of them will have the same center.
This means we cannot place four sheets of non-zero size without overlapping, so we return 0.
  • 来源
  • SRM 464
  • 操作

显示春菜