Submission #260451

#	Time	Username	Problem	Language	Result	Execution time	Memory
260451		georgerapeanu	Printed Circuit Board (CEOI12_circuit)	C++11	45 / 100	143 ms	8900 KiB

circuit

#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(det(origin,p[curr],p[ant]) == 0){
                ;
            }
            else if(seen[ant]){
                s.erase(segm_t(ant,curr));
            }
            else{
                s.insert(segm_t(curr,ant));
            }
            if(det(origin,p[curr],p[nxt]) == 0){
                ;
            }
            else if(seen[nxt]){
                s.erase(segm_t(nxt,curr));
            }
            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)

circuit.cpp: In function 'int main()':
circuit.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
circuit.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&p[i].first,&p[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 45 / 100