| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTITSU1B - Bài B - PTIT Summer 1 |
Nông dân John (FJ) muốn giám sát N con bò của mình (1 <= N <= 50,000) bằng cách sử dụng hệ thống giám sát mà ông ta mới mua.
Con bò thứ i đứng tại vị trí (x_i, y_i), trong đó các tọa độ đều là số tự nhiên (trong khoảng 0..1,000,000,000); không có con nào đứng cùng vị trí. Hệ thống giám sát của FJ gồm có ba máy quay, mỗi máy quay có thể quan sát tất cả các con bò dọc theo chiều dọc hoặc chiều ngang. Hãy giúp FJ tính toán xem có thể đặt ba chiếc máy quay để kiểm soát được N con bò hay không. Có nghĩa là hãy kiểm tra xem N con bò này có thể đồng thời được “phủ” bới tập ba đường thẳng, trong đó mỗi đường là đường ngang hoặc thẳng đứng.
Input
Dòng đầu tiên chứa số bộ test T. Sau đó là T bộ test, mỗi bộ test có dạng:
*Dòng 1: Số tự nhiên N
*Dòng 2..1+N: Dòng thứ i+1 chứa hai số tự nhiên cách nhau là x_i và y_i mô tả vị trí của con bò
Output
Mỗi bộ test in trên một dòng có dạng như sau:
*Dòng 1: In ra 1 nếu như có thể kiểm soát N con bò với ba máy quay, hoặc 0 nếu như không thể.
Example
Input:1
6
1 7
0 0
1 2
2 0
1 4
3 4 Output: 1
| Được gửi lên bởi: | adm |
| Ngày: | 2012-07-06 |
| Thời gian chạy: | 1.612s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2014-07-29 13:30:49 Hướng Thái Dương
cái này là đc phủ bởi đúng 3 đường thẳng hay là nhiều nhất 3 đương thẳng >? |
|
|
2013-01-18 12:39:02 Trần Vãn Dương D10CN2
Tử n^3 Chuyển n^2 Rồi cuối cùng nlogn Mấy AC |
|
|
2012-10-28 14:41:04 Trần Vãn Dương D10CN2
Last edit: 2012-11-09 09:11:03 |
|
|
2012-10-28 14:38:46 Trần Vãn Dương D10CN2
Last edit: 2012-11-09 09:11:12 |
