895 . 凸多邊形檢查器（駭客題）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

$Tyellow$

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

92.9% (13/14)

Tags

ioicamp ioicamp-2025

Description

在計算幾何題目中，常見的題目形式便是「輸入一凸多邊形」。什麼是凸多邊形呢？對於 $N$ 個點所圍成的簡單多邊形，如果多邊形內任兩點之間連成的直線都位於該多邊形內部，則我們就說這個多邊形是凸多邊形。而通常競賽程式會額外多加上一個限制：任意的相鄰三個點都不能共線。換句話說，凸多邊形的每個內角都是嚴格小於 $180^ \circ$ 的。

現在，波路特石做為題目的出題者，他必須要撰寫「測試資料檢查器」，顧名思義就是要寫程式確保測試資料的輸入符合題目敘述給出的限制。因此，當題目需要輸入凸多邊形時，他所撰寫的測試資料檢查器就需要檢查輸入是否為一凸多邊形。

為了簡化題目形式，我們假設波路特石先將他的檢查器拿去一道「請判斷輸入的 $N$ 個點是否形成凸多邊形」的題目去測試了。以下為波路特石提交的解法，請構造出一筆滿足題目條件的測試資料讓該程式碼 WA。

Code 
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define X first
#define Y second
typedef pair<long long, long long> pll;

pll operator-(pll a, pll b) 
{ return pll(a.X - b.X, a.Y - b.Y); }
long long cross(pll a, pll b) 
{ return a.X * b.Y - a.Y * b.X; }

int sign(long long a)
{ return a == 0 ? 0 : a > 0 ? 1 : -1; }
int ori(pll a, pll b, pll c) 
{ return sign(cross(b - a, c - a)); }

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<pll> convex(n);
    for (auto &[x, y] : convex)
        cin >> x >> y;

    auto bye = [&]() {
        cout << "No\n";
        exit(0);
    };

    for (int i = 0; i < n; ++i)
        if (ori(convex[i], convex[(i + 1) % n], convex[(i + 2) % n]) <= 0)
            bye();

    cout << "Yes\n";
}

Input Format

首行輸入一個正整數 $N$，代表多邊形的點數。

接下來 $N$ 行，第 $i$ 行包含兩個整數 $x_i$ 和 $y_i$，代表多邊形的第 $i$ 個點。

  • $3\leq N\leq 3000$
  • $-10^ 9\leq x_i, y_i\leq 10^ 9$
  • 保證任意相鄰三點不共線。
  • 保證任意兩點相異。

Output Format

若輸入的點形成一凸多邊形上點的逆時針順序，輸出 Yes，否則輸出 No。

Sample Input 1

3
0 0
1 0
0 1

Sample Output 1

Yes

Sample Input 2

3
0 0
0 1
1 0

Sample Output 2

No

Hints

波路特石的做法是：檢查多邊形的任意三個相鄰點是否形成嚴格小於 $180^ \circ$ 的內角，程式碼內的 ori(a, b, c) <= 0 就是用來檢查角 $abc$ 是否 $\geq 180^ \circ$ 的。

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料：

#include <stdio.h>
int main() {
    puts("3");
    puts("0 0");
    puts("1 0");
    puts("0 1");
}

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
Submit
Back to Top