Elearning CodePath – CTP Online Judge

Đếm điểm nguyên trong tam giác

DIEMNGUYEN

🟢 Hard #Geometry

### 📌 Thông tin chung

### 📝 Đề bài

Cho ba điểm không thẳng hàng $P(x_1, y_1)$, $Q(x_2, y_2)$ và $R(x_3, y_3)$ trên mặt phẳng tọa độ $Oxy$, với các tọa độ là những số nguyên. Một điểm được gọi là điểm nguyên (điểm lưới) nếu cả hoành độ và tung độ của nó đều là số nguyên.

Yêu cầu: Hãy tìm số lượng các điểm nguyên nằm hoàn toàn bên trong tam giác được tạo bởi ba điểm trên. Các điểm nằm trên cạnh của tam giác không được tính.

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file DIEMNGUYEN.INP:
* Gồm một dòng duy nhất chứa sáu số nguyên $x_1, y_1, x_2, y_2, x_3, y_3$ cách nhau bởi dấu cách.

### 📤 Định dạng Đầu ra

Ghi ra file DIEMNGUYEN.OUT:
* Một số nguyên duy nhất là số lượng điểm nguyên nằm bên trong tam giác.

### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| 0 0 0 5 5 0 | 6 |

Giải thích: 
Các điểm nguyên nằm bên trong tam giác là: (1,1), (1,2), (1,3), (2,1), (2,2) và (3,1).

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | Các tọa độ có giá trị tuyệt đối không quá 100 | 30% |
| 2 | Các tọa độ có giá trị tuyệt đối không quá 10^9 | 70% |

✅ Đã AC: 0 / 10 submissions