Rockdu's Blog

题目描述

Vicomte de Bajteaux is the owner of a renowned collection of boulders. Up to now, he has kept it in thecellars of his palace, but recently, he has decided to display the collection in his vast gardens.

The gardens have a shape of rectangle, whose sides are $1000000000$ units long and are parallel to east-westand north-south geographical directions. For each boulder, vicomte has determined coordinates ofthe point, which he would like it to be placed in (the coordinates are simply distances to the southern and western side of the garden), and gave them to his servants. Unfortunately he has forgot to tell them the orderof the coordinates (i.e. for some of the boulders the first coordinate of a point is the so called " $y$ coordinate",i.e. the ordinate, while for others the so called " $x$ coordinate", i.e. the abscissa).

The servants, unaware of thisfact, have placed the boulders assuming customary coordinate ordering (as in standard Cartesian coordinates:

the abscissa, commonly known as " $x$ coordinate", first).

To protect his collection, vicomte has decided to surround it with a fence. For aesthetic reasons thefence has to be a rectangle, with sides parallel to the sides of the garden. The garden layout has been planned, so that the total length of the fence be minimal (i.e. in the space of all coordinate orderings, the original ordering of vicomte requires the minimal length of the fence - we assume that the rectangle may have sides of zero length).

The servants have to move the boulders so that the length of the fence required is minimal lest their mistake become obvious. Each boulder may only be moved in a way that preserves the coordinate set: by interchanging its coordinates. As the boulders are heavy, the servants would like to minimize their effort, by minimizing the weight of the boulders to be moved.

Task

Write a programme which:

reads the present positions of the boulders in the gardens and their respective weights, determines a sequence of moves, which minimizes the length of the fence required to protect the boulders and also minimizes the weight of the boulders to be moved, writes the outcome to the standard output.

Blue Mary是一个有名的石头收藏家。迄今为止，他把他的藏品全部放在他的宫殿的地窖中。现在，他想将他的藏品陈列在他的花园中。皇家花园是一个边长为1000000000单位的平行于坐标轴的正方形。对于每个石头，Blue Mary都有一个他想放置的坐标，然后将他告诉他的属下。不幸的是，他忘了告诉他们坐标的顺序（比如无法分辨(x,y)和(y,x)）。属下们，就自己决定了每个石头的具体位置。为了保护他的藏品，Blue Mary决定建造一个篱笆来保护他们。为了美学的需要，篱笆也被设计为平行于坐标轴的矩形。如果花园的布局知道了，那么就可以知道最短长度的篱笆的布局。他的属下们需要变换石头的坐标使得篱笆的长度最少。每个石头只能从(x,y)变换为(y,x)，由于每个石头的重量不一样。属下们希望他们移动的石头的重量和最少。

输入输出格式

输入格式：

The first line of the standard input contains a single integer $n$ ( $2\le n\le 1000000$ ), denoting the number of boulders in the collection. The following $n$ lines contain three integers x_ixi​ , y_iyi​ and m_imi​ each ( 0≤xi​,yi​≤1 000 000 000 , $1\le m\le 2000$ ), separated by single spaces, denoting the present coordinates and the weight of $i$ 'th boulder. No unordered pair of coordinates will appear in the input more than once.

输出格式：

The first line of the standard output should contain two integers, separated by a single space - the minimal length of fence possible and the minimal weight of the boulders to be moved in order to obtain such a length.

The second line should contain a sequence of $n$ zeros and/or ones - $i$ 'th element of the sequence should be a one if in the optimal solution the i 'th boulder is to be moved and zero otherwise. Should more than one correct solutions exist, your programme is to write out any one of them.

输入输出样例

5
2 3 400
1 4 100
2 2 655
3 4 100
5 3 277

10 200
01010​​

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5, inf = 0x7fffffff;
int x[maxn], y[maxn], w[maxn];
int n, ans[4], mid, vis[4][maxn], mn[4][2] = {inf, inf, inf, inf, inf, inf, inf, inf};
int mx[4][2], id, mans = inf;

bool judge(int x, int y, int id) {
    swap(x, y);
    if(x < mn[id][0] || x > mx[id][0] || y < mn[id][1] || y > mx[id][1]) return false;
    return true;
}

int nx, ny;

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &x[i], &y[i], &w[i]);
        nx = x[i], ny = y[i];
        if(nx > ny) swap(nx, ny);
        mn[0][0] = min(mn[0][0], nx);
        mx[0][0] = max(mx[0][0], nx);
        mn[0][1] = min(mn[0][1], ny);
        mx[0][1] = max(mx[0][1], ny);
        mn[1][0] = min(mn[1][0], ny);
        mx[1][0] = max(mx[1][0], ny);
        mn[1][1] = min(mn[1][1], nx);
        mx[1][1] = max(mx[1][1], nx);
    }
    mn[2][0] = mn[1][0], mn[2][1] = mn[1][1];
    mx[2][0] = mx[0][0], mx[2][1] = mx[0][1];
    mn[3][0] = mn[0][0], mn[3][1] = mn[0][1];
    mx[3][0] = mx[1][0], mx[3][1] = mx[1][1];
    for(register int j = 0; j < 4; ++j)
        for(register int i = 1; i <= n; ++i) {
            if(!judge(x[i], y[i], j)) 
                vis[j][i] = 1, ans[j] += w[i];
        }
    for(register int i = 0; i < 4; ++i) if(mans > ans[i]) mans = ans[i], id = i;
    printf("%lld %d\n", 2LL * (mx[id][0] - mn[id][0] + mx[id][1] - mn[id][1]), ans[id]);
    for(register int i = 1; i <= n; ++i) {
        putchar('0' + (vis[id][i]));
    }
    return 0;
}