# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54972 | dfistric | Printed Circuit Board (CEOI12_circuit) | C++14 | 143 ms | 3520 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define point pair <int, int>
#define X first
#define Y second
#define ll long long
using namespace std;
const int MAXN = 100010;
struct line {
point A, B;
};
line lines[MAXN];
point ray;
multiset <line> s;
vector <point> ve;
vector <int> out;
int arr[MAXN];
int n;
ll ccw(point a, point b, point c) {
ll out = ((ll) a.X * (b.Y - c.Y)) +
((ll) b.X * (c.Y - a.Y)) +
((ll) c.X * (a.Y - b.Y));
return out;
}
ll ccw0(point a, point b) {
return ccw({0, 0}, a, b);
}
ll dist(point a) {
return (a.X * a.X) + (a.Y * a.Y);
}
bool operator==(line x, line y) {
return x.A == y.A && x.B == y.B;
}
bool operator< (line x, line y) {
if (x == y) return 0;
if (ccw0(x.A, x.B) < 0) swap(x.A, x.B);
if (ccw0(y.A, y.B) < 0) swap(y.A, y.B);
ll P = ccw(x.B, x.A, y.A) + ccw(x.B, y.A, y.B);
if (P == 0) {
if (x.A.Y == y.A.Y) return x.A.X < y.A.X;
return x.A.Y < y.A.Y;
}
return P > 0;
}
bool cmp(int a, int b) {
if (ccw0(ve[a], ve[b]) == 0) {
return ve[a] < ve[b];
}
return ccw0(ve[a], ve[b]) > 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin >> n;
REP(i, n) {
int a, b;
cin >> a >> b;
ve.push_back({a, b});
arr[i] = i;
}
sort(arr, arr + n, cmp);
//REP(i, n) cout << arr[i] + 1 << " "; cout << endl;
REP(ind, n) {
int i = arr[ind];
point x = ve[i];
ray = x;
for (int t : {-1, 1}) {
int j = (i + t + n) % n;
point y = ve[j];
if (cmp(i, j)) {
line tr = {x, y};
s.insert(tr);
}
}
line tr = *s.begin();
if (ccw(tr.A, tr.B, x) == 0) out.push_back(i);
for (int t : {-1, 1}) {
int j = (i + t + n) % n;
point y = ve[j];
if (!cmp(i, j)) {
line tr = {y, x};
s.erase(s.find(tr));
}
}
}
sort(out.begin(), out.end());
cout << out.size() << "\n";
for (int x : out) cout << x + 1 << " ";
cout << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |