fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. // Cấu trúc dữ liệu lưu trữ một điểm
  8. struct Point {
  9. int x, y, id; // Tọa độ của điểm và chỉ số ban đầu
  10. };
  11.  
  12. // Hàm tính cross product (tích có hướng) giữa ba điểm a, b, c
  13. // Cross product giúp xác định vị trí tương đối của điểm c so với đường thẳng a-b
  14. long long crossProduct(const Point& a, const Point& b, const Point& c) {
  15. return (long long)(b.x - a.x) * (c.y - a.y) - (long long)(b.y - a.y) * (c.x - a.x);
  16. }
  17.  
  18. // Hàm tính góc cực giữa điểm a (gốc) và điểm b
  19. // Góc cực là giá trị góc (theo radian) giữa trục x dương và đoạn thẳng a-b
  20. double polarAngle(const Point& a, const Point& b) {
  21. return atan2(b.y - a.y, b.x - a.x);
  22. }
  23.  
  24. int main() {
  25. int n; // Số lượng điểm
  26. cin >> n;
  27. vector<Point> points(n);
  28.  
  29. // Nhập tọa độ các điểm
  30. for (int i = 0; i < n; ++i) {
  31. cin >> points[i].x >> points[i].y;
  32. points[i].id = i + 1; // Lưu chỉ số của điểm (bắt đầu từ 1)
  33. }
  34.  
  35. // Duyệt qua từng điểm để xét làm điểm gốc (pivot point)
  36. for (int i = 0; i < n; ++i) {
  37. // Danh sách các điểm còn lại (không tính điểm gốc)
  38. vector<Point> others;
  39.  
  40. // Tạo danh sách các điểm khác điểm gốc
  41. for (int j = 0; j < n; ++j) {
  42. if (i != j) others.push_back(points[j]);
  43. }
  44.  
  45. // Sắp xếp các điểm theo góc cực so với điểm gốc points[i]
  46. sort(others.begin(), others.end(), [&](const Point& a, const Point& b) {
  47. return polarAngle(points[i], a) < polarAngle(points[i], b);
  48. });
  49.  
  50. // Sử dụng kỹ thuật quét góc để đếm số điểm ở mỗi phía
  51. // Số điểm bên trái đường thẳng
  52. int leftCount = 0;
  53. // Số điểm bên phải đường thẳng
  54. // (ban đầu là tất cả các điểm trừ điểm gốc và điểm đang xét)
  55. int rightCount = n - 2;
  56.  
  57. for (int j = 0; j < others.size(); ++j) {
  58. // Nếu số điểm ở hai phía bằng nhau, in kết quả và thoát chương trình
  59. if (leftCount == rightCount) {
  60. cout << points[i].id << " " << others[j].id << endl;
  61. return 0;
  62. }
  63.  
  64. // Di chuyển cửa sổ: cập nhật số lượng điểm ở hai phía khi xét đến điểm tiếp theo
  65. // Sử dụng cross product để xác định điểm others[j+1] nằm ở phía nào
  66. if (crossProduct(points[i], others[j], others[(j + 1) % others.size()]) > 0) {
  67. leftCount++; // Điểm mới thêm vào phía bên trái
  68. rightCount--; // Điểm bớt đi từ phía bên phải
  69. } else {
  70. leftCount--; // Điểm bớt đi từ phía bên trái
  71. rightCount++; // Điểm thêm vào phía bên phải
  72. }
  73. }
  74. }
  75.  
  76. return 0;
  77. }
Success #stdin #stdout 0.01s 5284KB
stdin
6
3 5
1 3
3 1
6 1
8 3
6 5
stdout
1 4