# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
260440 | georgerapeanu | Printed Circuit Board (CEOI12_circuit) | C++11 | 139 ms | 8944 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 <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int n;
pair<int,int> p[100005];
int ord[100005];
bool seen[100005];
const pair<int,int> origin = make_pair(0,0);
long long det(const pair<int,int> &a,const pair<int,int> &b,const pair<int,int> &c){
return 1LL * a.first * (b.second - c.second) + 1LL * b.first * (c.second - a.second) + 1LL * c.first * (a.second - b.second);
}
pair<int,int> dir;
pair<int,int> nxt_dir;
struct segm_t{
int i,j;
long long a,b,c;
segm_t(int i,int j){
this->i = i;
this->j = j;
a = p[j].second - p[i].second;
b = p[i].first - p[j].first;
c = 1LL * p[j].first * p[i].second - 1LL * p[i].first * p[j].second;
}
bool operator < (const segm_t &other)const{
///-c/(a * dir.first + b * dir.second) < -other.c / (other.a * dir.first + other.b * dir.second);
int sgn = (a * dir.first + b * dir.second > 0 ? 1:-1) * (other.a * dir.first + other.b * dir.second > 0 ? 1:-1);
long long fst = sgn * c * (other.a * dir.first + other.b * dir.second);
long long snd = sgn * other.c * (a * dir.first + b * dir.second);
if(fst != snd){
return fst > snd;
}
else{
pair<int,int> dir = nxt_dir;
int sgn = (a * dir.first + b * dir.second > 0 ? 1:-1) * (other.a * dir.first + other.b * dir.second > 0 ? 1:-1);
long long fst = sgn * c * (other.a * dir.first + other.b * dir.second);
long long snd = sgn * other.c * (a * dir.first + b * dir.second);
if(fst != snd){
return fst > snd;
}
else{
return 1LL * p[j].second * p[j].second + 1LL * p[j].first * p[j].first < 1LL * p[other.j].first * p[other.j].first + 1LL * p[other.j].second * p[other.j].second;
}
}
}
bool is_good(const int &point)const{
return det(p[i],p[j],p[point]) >= 0;
}
};
set<segm_t> s;
bool cmp(const int &a,const int &b){
return det(origin,p[a],p[b]) > 0;
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d %d",&p[i].first,&p[i].second);
ord[i] = i;
}
sort(ord + 1,ord + 1 + n,cmp);
vector<int> ans;
for(int i = 1;i <= n;i++){
dir = p[ord[i]];
int j = i + 1;
while(j <= n && cmp(ord[i],ord[j]) == 0){
j++;
}
j--;
nxt_dir = p[ord[j + 1]];
for(int k = i;k <= j;k++){
int curr = ord[k];
int ant = (curr == 1 ? n:curr - 1);
int nxt = (curr == n ? 1:curr + 1);
///TODO check colinearity of curr,nxt,ant to not erase stuff twice or smth
if(seen[ant]){
s.erase(segm_t(ant,curr));
}
else{
}
if(seen[nxt]){
s.erase(segm_t(nxt,curr));
}
else{
}
}
for(int k = i;k <= j;k++){
int curr = ord[k];
int ant = (curr == 1 ? n:curr - 1);
int nxt = (curr == n ? 1:curr + 1);
///TODO check colinearity of curr,nxt,ant to not erase stuff twice or smth
if(seen[ant]){
}
else{
s.insert(segm_t(curr,ant));
}
if(seen[nxt]){
}
else{
s.insert(segm_t(curr,nxt));
}
}
int closest = -1;
for(int k = i;k <= j;k++){
if(closest == -1 || p[ord[k]].first < p[closest].first){
closest = ord[k];
}
}
if(s.empty() == true){
ans.push_back(closest);
}
else{
if(s.begin()->is_good(closest)){
ans.push_back(closest);
}
}
for(int k = i;k <= j;k++){
seen[ord[k]] = true;
}
i = j;
}
printf("%d\n",(int)ans.size());
sort(ans.begin(),ans.end());
for(auto it:ans){
printf("%d ",it);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |