fork download
  1. #include <bits/stdc++.h>
  2. using ll = long long;
  3. using namespace std;
  4.  
  5. struct line {
  6. float k, b;
  7. bool operator<(const line &other) const {
  8. if (k == other.k) return b < other.b;
  9. return k < other.k;
  10. }
  11. };
  12. struct pudge {
  13. ll x, y, i;
  14. bool operator<(const pudge &other) const {
  15. if (x == other.x) return y < other.y;
  16. return x < other.x;
  17. }
  18. };
  19.  
  20. void sol() {
  21. ll n, m; cin >> n >> m;
  22. vector<pudge> p(n);//координаты
  23. vector<bool> alive(n), dang(n);//dang = 1 - есть крюк
  24. for (int i = 0; i < n; i++) {
  25. cin >> p[i].x >> p[i].y;
  26. p[i].i = i;
  27. alive[i] = 1;
  28. dang[i] = 1;
  29. }
  30. map<line, set<pudge>> mp;
  31. for (int i = 0; i < n; i++) {
  32. for (int j = i + 1; j < n; j++) {
  33. ll x1 = p[i].x, y1 = p[i].y; //делаем прямую
  34. ll x2 = p[j].x, y2 = p[j].y;
  35. float k, b;
  36. if (x1 == x2) {
  37. k = 1e18, b = x1;
  38. } else {
  39. k = (float)(y2 - y1) / (x2 - x1);
  40. b = (float)y1 - k * x1;
  41. }
  42. mp[{k, b}].insert({x1, y1, i});
  43. mp[{k, b}].insert({x2, y2, j});
  44. }
  45. }
  46. while (m--) {
  47. ll at, def; cin >> at >> def; at--; def--;
  48. if (dang[at] == 0 || alive[at] == 0) continue;//атакующий метв/безоружен идем дальше
  49. ll x1 = p[at].x, y1 = p[at].y;
  50. ll x2 = p[def].x, y2 = p[def].y;
  51. float k, b; //делаем прямую
  52. if (x1 == x2) {
  53. k = 1e18, b = x1;
  54. } else {
  55. k = (float)(y2 - y1) / (x2 - x1);
  56. b = (float)y1 - k * x1;
  57. }
  58. set<pudge> points = mp[{k, b}];
  59. auto it = points.find({x1, y1});
  60. if (x1 < x2 || (x1 == x2 && y1 < y2)) { //в каком направлении крюк летел?
  61. it++;
  62. while (it != points.end()) {
  63. pudge pud = *it;
  64. if (alive[pud.i] == 1) {
  65. alive[pud.i] = 0;
  66. break;
  67. }
  68. it++;
  69. }
  70. if (it == points.end()) dang[at] = 0;
  71. }
  72. else if (x1 > x2 || (x1 == x2 && y1 > y2)) { //аналогично только назад
  73. it--;
  74. while (it != points.begin()) {
  75. pudge pud = *it;
  76. if (alive[pud.i] == 1) {
  77. alive[pud.i] = 0;
  78. break;
  79. }
  80. it--;
  81. }
  82. if (it == points.begin()) {
  83. pudge pud = *it;
  84. if (alive[pud.i] == 0) dang[at] = 0;
  85. else alive[pud.i] = 0;
  86. }
  87. }
  88. }
  89. ll sz = 0;
  90. for (auto i : alive) sz += i;
  91. cout << sz << '\n';
  92. for (int i = 0; i < n; i++) {
  93. if (alive[i] == 1) cout << i + 1 << " ";
  94. }
  95. }
  96.  
  97. int main() {
  98. //freopen("input.txt", "r", stdin);
  99. //freopen("output.txt", "w", stdout);
  100. ios::sync_with_stdio(0);
  101. cin.tie(0);
  102. ll t = 1;
  103. //cin >> t;
  104. while (t--) sol();
  105. return 0;
  106. }
Success #stdin #stdout 0.01s 5276KB
stdin
3 3
0 0
1 3
3 1
1 2
3 2
3 1
stdout
2
1 3