Byteland có \(n\) thành phố (\(n\ge3\)), mỗi thành phố được biểu diễn bởi một điểm khác nhau trên mặt phẳng. Các thành phố được đánh số từ \(1\) đến \(n\). Không có ba thành phố nào thẳng hàng.

Bọc lồi của một tập điểm là đa giác lồi có diện tích nhỏ nhất sao cho mọi điểm đều nằm bên trong hoặc trên biên đa giác. Đa giác lồi có mọi góc nhỏ hơn \(180\) độ và không tự cắt. Hãy tìm số thành phố nằm trên biên của bọc lồi.

Bạn không biết tọa độ các thành phố. Thay vào đó, bạn được phép hỏi hướng quay của bộ ba thành phố phân biệt \((i,j,k)\). Câu trả lời cho biết thứ tự đi qua ba thành phố đó là theo chiều kim đồng hồ hay ngược chiều kim đồng hồ.

Giao diện

Đề gốc dùng thư viện để bài làm truy vấn hướng quay và gửi đáp án. Trên LQDOJ, chương trình vẫn dùng giao diện chữ ký hàm: với C++, bài làm phải định nghĩa void solve(); với Java, bài làm phải định nghĩa static void solve() trong lớp Solution.

Đây là bản chuyển thể trên LQDOJ; bộ kiểm thử được tạo riêng và không phải bộ dữ liệu bí mật chính thức của CEOI 2018.

Grader cung cấp các hàm sau:

int get_n();
bool is_clockwise(int a, int b, int c);
void give_answer(int s);

Với Java, grader cung cấp lớp trilib với các phương thức tĩnh get_n(), is_clockwise(int a, int b, int c) và give_answer(int s) có cùng ý nghĩa.

• get_n() trả về số thành phố.
• is_clockwise(a,b,c) trả về true nếu thứ tự \((a,b,c)\) theo chiều kim đồng hồ, ngược lại trả về false. Ba chỉ số phải đôi một khác nhau và thuộc đoạn \([1,n]\).
• give_answer(s) thông báo rằng có \(s\) thành phố trên biên bọc lồi.

Sau khi gọi give_answer, chương trình phải kết thúc ngay. Hàm này phải được gọi đúng một lần. Không được đọc dữ liệu từ đầu vào chuẩn hoặc ghi dữ liệu ra đầu ra chuẩn.

Các tọa độ được cố định trong suốt quá trình chạy; thư viện trả lời truy vấn một cách xác định. Bạn có thể thử đoán đáp án ngay cả khi chưa chắc chắn.

Dữ liệu vào

Grader đọc dữ liệu kiểm thử trước khi gọi solve(). Bài làm không được đọc dữ liệu từ đầu vào chuẩn.

Dữ liệu ra

Bài làm không được ghi dữ liệu ra đầu ra chuẩn; hãy gọi give_answer(s) đúng một lần.

Thư viện công khai kèm theo đề gốc đọc dữ liệu gồm số thành phố \(n\), sau đó là \(n\) cặp tọa độ. Thư viện này chỉ phục vụ thử nghiệm và khác với thư viện bí mật dùng trên hệ thống chấm chính thức.

Ví dụ

Trong ví dụ, có \(6\) thành phố tại các tọa độ \((1,1)\), \((4,3)\), \((2,2)\), \((1,4)\), \((5,1)\) và \((3,2)\). Bọc lồi có \(4\) đỉnh.

Một số lời gọi tương ứng với ví dụ:

Phân nhóm

Trong tất cả các bộ dữ liệu, \(3\le n\le40000\). Bạn được gọi is_clockwise nhiều nhất \(1000000\) lần.

1. \(15\) điểm: \(n\le50\).
2. \(20\) điểm: \(n\le500\).
3. \(20\) điểm: \(n\le15000\).
4. \(20\) điểm: Có nhiều nhất một thành phố không nằm trên biên bọc lồi.
5. \(25\) điểm: Không có ràng buộc bổ sung.