Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOMOVREC - Di chuyển hình chữ nhật

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vomovrec


Cho N hình chữ nhật trên mặt phẳng Oxy. Các hình chữ nhật này có toạ độ nguyên và có các cạnh song song với trục toạ độ. Ở mỗi lượt, các hình chữ nhật có thể đứng yên hoặc di chuyển theo 8 hướng:

  • sang trái 1 đơn vị
  • sang phải 1 đơn vị
  • lên trên 1 đơn vị
  • xuống dưới 1 đơn vị
  • sang trái và lên trên 1 đơn vị
  • sang trái và xuống dưới 1 đơn vị
  • sang phải và lên trên 1 đơn vị
  • sang phải và xuống dưới 1 đơn vị

Hãy xác định sau ít nhất bao nhiên lượt thì N hình chữ nhật ban đầu sẽ được di chuyển đến các vị trí mới sao cho phần diện tích giao nhau của tất cả N hình chữ nhật này lớn hơn hoặc bằng 1.

Dữ liệu vào

Dòng đầu tiên ghi số N là số lượng các hình chữ nhật.

Tiếp theo là N dòng, mỗi dòng ghi 4 số nguyên x1, y1, x2, y2 thể hiện hình chữ nhật có góc trái dưới là (x1, y1) góc phải trên là (x2, y2).

Dữ liệu ra

In ra số lượt di chuyển tối thiểu.

Giới hạn

Subtask 1 (30% số điểm)

  • 2 ≤ N ≤ 200
  • |tọa độ| ≤ 100
  • Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 2 (40% số điểm)

  • 200 < N ≤ 105
  • |toạ độ| ≤ 2 * 109
  • Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 3 (30% số điểm)

  • 200 < N ≤ 105
  • |tọa độ| ≤ 2 * 109

Ví dụ

Input:
3
0 0 1 1
0 0 2 3
2 3 4 5
Output:
2

Giải thích

 

Sau 2 lượt:

  • Hình 1: Di chuyển lên trên 1 đơn vị rồi sau đó di chuyển chéo lên phải 1 đơn vị.
  • Hình 2: Đứng yên.
  • Hình 3: Di chuyển chéo xuống trái 1 đơn vị.

Được gửi lên bởi:VOJ Team
Ngày:2015-12-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14 PAS-GPC PAS-FPC TEXT
Nguồn bài:VNOI Online 2016

hide comments
2017-11-09 03:06:57
tham khảo thuật toán tại http://bfy.tw/Evte
2017-11-09 03:06:55
Đ** Cụ thằng bên trên

Last edit: 2017-11-09 03:07:40
2017-11-09 03:04:51
Lấy sol tại : http://bfy.tw/EvtY
2017-11-09 03:03:57
Code tham khảo: #include <algorithm>
#include <cstdio>

typedef long long llint;

enum direction { LEFT, RIGHT, DOWN, UP };

struct point {
llint x, y;
bool flag;
point *next[4];
point *CCW, *CW;

point() {
flag = false;
for( int i = 0; i < 4; ++i ) next[i] = NULL;
CCW = CW = NULL;
}
};

int ccw( point *A, point *B, point *C ) {
llint t = (B->x-A->x)*(C->y-A->y) - (C->x-A->x)*(B->y-A->y);
if( t < 0 ) return -1;
if( t > 0 ) return 1;
return 0;
}

bool cmp_x( point *A, point *B ) { return A->x < B->x; }
bool cmp_y( point *A, point *B ) { return A->y < B->y; }

void connect( int n, point **order, point **extreme, direction A, direction B ) {
extreme[A] = order[0];
extreme[B] = order[n-1];
for( int i = 1; i < n; ++i ) {
order[i]->next[A] = order[i-1];
order[i-1]->next[B] = order[i];
}
}

void go_inwards( char *chosen, point **order, int steps, point **extreme ) {
for( int i = 0; i < steps; ++i ) {
if( chosen[i] == 'L' ) order[i] = extreme[LEFT];
if( chosen[i] == 'R' ) order[i] = extreme[RIGHT];
if( chosen[i] == 'D' ) order[i] = extreme[DOWN];
if( chosen[i] == 'U' ) order[i] = extreme[UP];

order[i]->flag = 1;

for( int d = 0; d < 4; ++d )
while( extreme[d]->flag )
extreme[d] = extreme[d]->next[d^1];
}
}

void add( llint &area, point *P ) {
P->CCW->CW = P;
P->CW->CCW = P;
area += P->x * P->CCW->y - P->y * P->CCW->x;
area += P->CW->x * P->y - P->CW->y * P->x;
area -= P->CW->x * P->CCW->y - P->CW->y * P->CCW->x;
}
void sub( llint &area, point *P ) {
P->CCW->CW = P->CW;
P->CW->CCW = P->CCW;
area -= P->x * P->CCW->y - P->y * P->CCW->x;
area -= P->CW->x * P->y - P->CW->y * P->x;
area += P->CW->x * P->CCW->y - P->CW->y * P->CCW->x;
}

llint *go_outwards( char *chosen, point **order, int steps, point **extreme ) {
llint *result = new llint[steps];

llint area = 0;

for( int i = steps-1; i >= 0; --i ) {
direction d;
if( chosen[i] == 'L' ) d = LEFT;
if( chosen[i] == 'R' ) d = RIGHT;
if( chosen[i] == 'D' ) d = DOWN;
if( chosen[i] == 'U' ) d = UP;

point *A = order[i];

for( A->CCW = extreme[d]; A->CCW != extreme[d^1] && ccw( A, A->CCW, A->CCW->CCW ) <= 0; A->CCW = A->CCW->CCW )
if( A->CCW != extreme[d] ) sub( area, A->CCW );
for( A->CW = extreme[d]; A->CW != extreme[d^1] && ccw( A, A->CW, A->CW->CW ) >= 0; A->CW = A->CW->CW )
if( A->CW != extreme[d] ) sub( area, A->CW );

if( A->CW != extreme[d] && A->CCW != extreme[d] ) sub( area, extreme[d] );

add( area, A );

if( A->x < extreme[LEFT]->x ) extreme[LEFT] = A;
if( A->x > extreme[RIGHT]->x ) extreme[RIGHT] = A;
if( A->y < extreme[DOWN]->y ) extreme[DOWN] = A;
if( A->y > extreme[UP]->y ) extreme[UP] = A;

result[i] = area;
}

return result;
}

typedef point * ppoint;

int main( void ) {
int n;
scanf( "%d", &n );
point *data = new point[n];
for( int i = 0; i < n; ++i ) scanf( "%lld%lld ", &data[i].x, &data[i].y );

point **order = new ppoint[n];
for( int i = 0; i < n; ++i ) order[i] = data + i;

point *extreme[4];
std::sort( order, order+n, cmp_x ); connect( n, order, extreme, LEFT, RIGHT );
std::sort( order, order+n, cmp_y ); connect( n, order, extreme, DOWN, UP );

char *chosen = new char[n];
gets( chosen );

go_inwards( chosen, order, n-2, extreme );

extreme[LEFT]->CCW = extreme[LEFT]->CW = extreme[RIGHT];
extreme[RIGHT]->CCW = extreme[RIGHT]->CW = extreme[LEFT];

llint *result = go_outwards( chosen, order, n-2, extreme );

for( int i = 0; i < n-2; ++i ) printf( "%lld.%lld\n", result[i]>>1, (result[i]&1)*5 );

delete[] order;
delete[] data;
delete[] chosen;
delete[] result;

return 0;
}

2017-11-09 03:03:34
Sao sub mãi vẫn được có 100!!!
Nản quá các bác ạ @@ ^_^
2017-11-09 03:00:26
Thánh nào k AC bài này chết mẹ đi cho đỡ nhục
2017-11-09 03:00:04
Đề dễ vãi lồn các bác ạ
2017-11-09 02:26:20
100 là AC chưa các bác
2017-11-09 02:18:39
Trâu cũng AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.