# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
119299 | tmwilliamlin168 | Printed Circuit Board (CEOI12_circuit) | C++14 | 66 ms | 20860 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>
using namespace std;
#define ll long long
const int mxN=1e5;
int n, b[mxN], c[mxN+1], e1[mxN], e2[mxN];
array<ll, 2> a[mxN+1];
vector<int> va[mxN], vr[mxN], vp[mxN], ans;
bool cw(int x, int y, int z) {
return (a[z][1]-a[x][1])*(a[y][0]-a[x][0])<(a[y][1]-a[x][1])*(a[z][0]-a[x][0]);
}
bool pcmp(const int &i, const int &j) {
return a[i][1]*a[j][0]<a[j][1]*a[i][0];
}
struct scmp {
bool operator()(const int &i, const int &j) const {
if(e1[i]==e1[j])
return c[e2[i]]<c[e2[j]]?!cw(e1[j], e2[j], e2[i]):cw(e1[i], e2[i], e2[j]);
return c[e1[i]]<c[e1[j]]?cw(e1[i], e2[i], e1[j]):!cw(e1[j], e2[j], e1[i]);
}
};
set<int, scmp> s;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; ++i)
cin >> a[i][0] >> a[i][1];
//a[n]=a[0];
iota(b, b+n, 0);
sort(b, b+n, pcmp);
for(int i=0; i<n; ++i) {
c[i]=lower_bound(b, b+n, i, pcmp)-b;
//vp[c[i]].push_back(i);
}
//c[n]=c[0];
return 0;
for(int i=0; i<n; ++i) {
e1[i]=i;
e2[i]=i+1;
if(c[e2[i]]<c[e1[i]])
swap(e1[i], e2[i]);
if(c[e1[i]]<c[e2[i]]) {
va[c[e1[i]]].push_back(i);
vr[c[e2[i]]].push_back(i);
}
}
for(int i=0; i<n; ++i) {
for(int j : vr[i])
s.erase(j);
for(int j : va[i])
s.insert(j);
int mj=-1;
for(int j : vp[i])
if(mj<0||a[j][0]+a[j][1]<a[mj][0]+a[mj][1])
mj=j;
if(~mj&&(!s.size()||!cw(e1[*s.begin()], e2[*s.begin()], mj)))
ans.push_back(mj);
}
cout << ans.size() << "\n";
sort(ans.begin(), ans.end());
for(int a : ans)
cout << a+1 << " ";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |