Submission #932506

#	Time	Username	Problem	Language	Result	Execution time	Memory
932506		n0sk1ll	Printed Circuit Board (CEOI12_circuit)	C++17	10 / 100	46 ms	9208 KiB

circuit

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

int x[100005],y[100005];
int ord[100005]; //order of the point

li dot(int a, int b, int c, int d)
{
    return (li)a*d-(li)b*c;
}

struct mojsort
{
    bool operator() (pair<pii,int> x, pair<pii,int> y)
    {
        return dot(x.xx.xx,x.xx.yy,y.xx.xx,y.xx.yy)>0;
    }
};

int N;
int fwt[100005];

void add(int i, int x)
{
    for (;i<=N;i+=(i&-i)) fwt[i]+=x;
}

int pre(int i)
{
    int ret=0;
    for (;i;i-=(i&-i)) ret+=fwt[i];
    return ret;
}

main()
{
    FAST;

    int n; cin>>n;
    ff(i,0,n) cin>>x[i]>>y[i];

    vector<pair<li,int>> tacke;
    ff(i,0,n) tacke.push_back({-((li)x[i]*x[i] + (li)y[i]*y[i]),i});
    sort(all(tacke));

    vector<pair<li,int>> duzi;
    ff(i,0,n)
    {
        int j=(i+1)%n;
        li d=max((li)x[i]*x[i]+(li)y[i]*y[i],(li)x[j]*x[j]+(li)y[j]*y[j]);
        duzi.push_back({-d,i});
    }
    sort(all(duzi));

    vector<pair<pii,int>> uglovi;
    ff(i,0,n) uglovi.push_back({{x[i],y[i]},i});
    sort(all(uglovi),mojsort());

    int idx=0;
    ff(i,0,n)
    {
        if (i==0 || dot(uglovi[i-1].xx.xx,uglovi[i-1].xx.yy,uglovi[i].xx.xx,uglovi[i].xx.yy)) ++idx;
        ord[uglovi[i].yy]=idx;
    }
    N=idx;

    vector<int> ans;

    while (!tacke.empty() && !duzi.empty())
    {
        if (tacke.back().xx >= duzi.back().xx)
        {
            if (pre(ord[tacke.back().yy])==0)
            {
                ans.pb(tacke.back().yy+1);
            }
            tacke.popb();
        }
        else
        {
            int i=duzi.back().yy;
            int j=(i+1)%n;
            int l=ord[i];
            int r=ord[j];
            if (l>r) swap(l,r);
            add(l,1);
            add(r+1,-1);
            duzi.popb();
        }
    }

    sort(all(ans));
    cout<<(int)ans.size()<<"\n";
    for (auto it : ans) cout<<it<<" ";
}

Compilation message (stderr)

circuit.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main()
      | ^~~~

• Subtask 1: 10 / 100