Submission #632480

#	Time	Username	Problem	Language	Result	Execution time	Memory
632480		andrei_boaca	Printed Circuit Board (CEOI12_circuit)	C++14	30 / 100	166 ms	11676 KiB

circuit

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n;
struct point
{
    int x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].x!=v[b].x)
        return v[a].x<v[b].x;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    sort(angle+1,angle+n+1,comp);
   // cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }
    vector<int> ind;
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),cmp);
    vector<int> sol;
    for(int i:ind)
    {
        int cnt=suma(v[i].ang)-times[i];
        if(cnt==0&&spec[v[i].ang]==0)
            sol.push_back(i);
        spec[v[i].ang]=1;
        int lft=i-1;
        if(i==1)
            lft=n;
        if(!use[lft])
        {
            int st=v[i].ang;
            int dr=v[lft].ang;
            if(st>dr)
                swap(st,dr);
            update(st,1);
            update(dr+1,-1);
            times[lft]++;
        }
        int rgt=i+1;
        if(i==n)
            rgt=1;
        if(!use[rgt])
        {
            int st=v[i].ang;
            int dr=v[rgt].ang;
            if(st>dr)
                swap(st,dr);
            update(st,1);
            update(dr+1,-1);
            times[rgt]++;
        }
        use[i]=1;
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

• Subtask 1: 30 / 100