Approach
Sorting and greedy selection
For ABC181 C — Collinearity, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 41 lines of C++ from the credited upstream file abc181_c.cpp.
- The implementation visibly relies on sequence storage.
- 4 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <vector>4 5using namespace std;6using ui = unsigned int;7 8bool comp(pair<double, double>& l, pair<double, double>& r) {9 return l.first < r.first;10}11 12int main() {13 ui n;14 cin >> n;15 16 vector<pair<double, double>> xy(n);17 for (auto& z : xy) cin >> z.first >> z.second;18 19 sort(xy.begin(), xy.end(), comp);20 21 for (ui i = 0; i < n; i++) {22 for (ui j = i + 1; j < n; j++) {23 for (ui k = j + 1; k < n; k++) {24 if ((xy[i].first == xy[j].first &&25 xy[j].first == xy[k].first) ||26 (xy[i].second == xy[j].second &&27 xy[j].second == xy[k].second) ||28 (xy[j].second - xy[i].second) /29 (xy[j].first - xy[i].first) ==30 (xy[k].second - xy[j].second) /31 (xy[k].first - xy[j].first)) {32 cout << "Yes" << endl;33 return 0;34 }35 }36 }37 }38 39 cout << "No" << endl;40 return 0;41}