Thảo luậnSnackDown Online Qualifier 2017 - Same Snake

Trong lưới 2D, các ô được xác định bởi (i, j). Bạn đã nhận được thông tin về hình ảnh của hai con rắn trong bản đồ. Bạn muốn kiểm tra xem chúng có thể là hình ảnh của một con rắn hay không.

Mỗi hình con rắn được cho bằng một đoạn thẳng trong lưới mà bạn đã biết điểm đầu và điểm cuối. Giờ hãy xem mỗi ô của lưới là một đỉnh. Có một cạnh giữa hai đỉnh khi và chỉ khi hai đỉnh là hai ô kề nhau trong hình ảnh của ít nhất một con rắn. Tức là, với ít nhất một con rắn, khi bạn đi từ đầu này tới đầu kia, hai ô kề nhau sẽ xuất hiện liên tục.

Hình ảnh hai con rắn có thể gộp làm một nếu thỏa mãn các điều kiện sau đây:

- Tập hợp các ô của con rắn đầu tiên và con rắn thứ hai tạo thành một thành phần liên

thông.

- Không có đỉnh nào có bậc lớn hơn 2 trong đồ thị.

Nói cách khác, kết hợp hai thành phần phải tạo thành một đường đi.

Dữ liệu vào

- Dòng đầu tiên chứa một số nguyên T là số lượng test. Các test được miêu tả như sau

- Dòng đầu tiên của mỗi test chứa bốn số nguyên X11, Y11, X12, Y12 thể hiện hai đầu mút của con rắn đầu tiên là (X11, Y11) và (X12, Y12).

- Dòng thứ hai của mỗi test chứa bốn số nguyên X21, Y21, X22, Y22 thể hiện hai đầu mút của con rắn thứ hai là (X21, Y21) và (X22, Y22).

Dữ liệu ra

- Với mỗi test, in ra “yes” nếu hai con rắn có thể gộp lại như định nghĩa bên trên, và “no”

trong trường hợp ngược lại.

Ràng buộc

- 1 ≤ T ≤ 10^5

- -10^9 ≤ Xij,Yij ≤ 10^9

- Hai đầu mút của rắn được đảm bảo là cùng một dòng hoặc cùng một cột và các con rắn chiếm tất cả những ô ở giữa, kể cả hai đầu mút.

Vı́ dụ

Input:

7 4
2 1 8 1
11 1 7 1
2 1 8 1
11 1 9 1
2 1 8 1
3 1 3 -2
2 1 8 1
2 1 2 -2

Output:

yes
no
no
yes

Giải thích

Trong các hình, con rắn đầu tiên có màu đỏ, con rắn thứ hai có màu vàng và nếu có đoạn trùng nhau thì chúng có màu cam.

Test đầu tiên tương ứng với

Cả hai đầu kiện đều thỏa mãn nên đáp án là “yes”.

Test thứ hai tương ứng với

Không có cạnh nào ở giữa hai đỉnh tương ứng với ô (8, 1) và ô (9, 1). Do đó kết hợp lại không

thành đồ thị liên thông nên đáp án là “no”.

Test thứ ba tương ứng với

Đỉnh tương ứng với ô (3, 1) có bậc là 3, lớn hơn 2 nên đáp án là “no”

Test thứ tư tương ứng với

Thỏa mãn các điều kiện nên đáp án là “yes”

____________

Time Limit: 1 secs

Source Limit: 50000 Bytes

Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

Thiếu điều kiện nào không nhỉ :10:

#include<bits/stdc++.h>
  using namespace std;
 
int t, x11, y11, x12, y12, x21, y21, x22, y22;
int main()
{
    scanf("%d", &t);
    while (t--) // loop for testcases
    {
        scanf("%d %d %d %d", &x11, &y11, &x12, &y12);
        scanf("%d %d %d %d", &x21, &y21, &x22, &y22);
        // Same row
        if (x11 == x12 && x11 == x21 && x11 == x22) {
            if ((y11 <= max(y21, y22) && y11 >= min(y21, y22)) || (y12 <= max(y21, y22) && y12 >= min(y21, y22))) {
                cout << "yes\n"; continue;
            } else {
                cout << "no\n"; continue;
            }
        }
        // Same column
        if (y11 == y12 && y11 == y21 && y11 == y22) {
            if ((x11 <= max(x21, x22) && x11 >= min(x21, x22)) || (x12 <= max(x21, x22) && x12 >= min(x21, x22))) {
                cout << "yes\n"; continue;
            } else {
                cout << "no\n"; continue;
            }
        }
        // different row or collumn
        if (
            (x11 == x21 && y11 == y21) ||
            (x11 == x22 && y11 == y22) ||
            (x12 == x21 && y12 == y21) ||
            (x12 == x22 && y12 == y22)
        ) {
            cout << "yes\n"; continue;
        }
        cout << "no\n";
    }
    return 0;
}

bài này ez

sao vẫn lỗi nhỉ