fork download
copy 
  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
comments (?)
stdin
copy 
3 3
0 0
1 3
3 1
1 2
3 2
3 1
stdout
copy 
2
1 3
https://ideone.com/CWIeC3
language:
C++14 (gcc 8.3)
created:
82 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!