fork download
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct Point {
  6. int x, y; // Tọa độ của điểm
  7. };
  8.  
  9. int main() {
  10. int n;
  11. cin >> n; // Nhập số lượng điểm (luôn là số chẵn)
  12. vector<Point> points(n); // Lưu trữ danh sách các điểm
  13. for (int i = 0; i < n; ++i) {
  14. cin >> points[i].x >> points[i].y; // Nhập tọa độ của từng điểm
  15. }
  16.  
  17. // Duyệt qua tất cả các cặp điểm (i, j)
  18. for (int i = 0; i < n; ++i) {
  19. for (int j = i + 1; j < n; ++j) {
  20. // Đếm số điểm ở hai phía của đường thẳng
  21. int count_pos = 0, count_neg = 0;
  22.  
  23. for (int k = 0; k < n; ++k) {
  24. // Bỏ qua hai điểm đang xét (i, j)
  25. if (k == i || k == j) continue;
  26.  
  27. // Tính giá trị cross product để xác định vị trí của điểm k
  28. // (y2 - y1) * (x - x1) - (x2 - x1) * (y - y1)
  29. long long val = (points[j].y - points[i].y)
  30. * (points[k].x - points[i].x)
  31. - (points[j].x - points[i].x)
  32. * (points[k].y - points[i].y);
  33. // Điểm k nằm ở một phía (phía dương)
  34. if (val > 0) count_pos++;
  35. // Điểm k nằm ở phía còn lại (phía âm)
  36. else if (val < 0) count_neg++;
  37. }
  38.  
  39. // Nếu số điểm ở hai phía bằng nhau, in ra cặp điểm (i, j)
  40. if (count_pos == count_neg) {
  41. // In chỉ số của hai điểm (theo thứ tự nhập)
  42. cout << i + 1 << " " << j + 1 << endl;
  43. // Thoát chương trình vì đã tìm thấy đáp án
  44. return 0;
  45. }
  46. }
  47. }
  48.  
  49. return 0;
  50. }
Success #stdin #stdout 0s 5292KB
stdin
6
3 5
1 3
3 1
6 1
8 3
6 5
stdout
1 4