13052022-04-15 12:46:33k_balintHázakcpp14Accepted 100/100167ms38456 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100005;

struct pnt{
    ll x,y;
    pnt(ll xx, ll yy){
        x=xx; y=yy;
    }
    pnt(){x=y=0;}
};

pnt O=pnt(0,0);
int turn(const pnt &a,const pnt &b, const pnt &c){
    ll k=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    return (k>0)-(k<0);
}

bool l(const pnt &a, const pnt &b){
    return a.y<b.y || (a.y==b.y && a.x<b.x);
}

struct seg{
    pnt A,B;
    seg(pnt a, pnt b){
        A=a; B=b;
    }
    seg(){A=B=pnt();}
};

struct ev{
    pnt A,B; int t,id;
    ev(pnt a, pnt b, int tt, int i){
        A=a; B=b; t=tt; id=i;
    }
    ev(){A=B=pnt(); t=id=0;}

    bool operator < (const ev& o) const {
        int ang=turn(O,A,o.A);
        if(ang != 0) return ang>0;
        if(t != o.t) return t<o.t;

        if(t==0) return l(A,o.A);
        return !l(A,o.A);
    }
};

seg arr[MAXN];
struct cmp{
    int id;

    cmp(int i){id=i;}
    cmp(){id=0;}

    bool operator<(const cmp& o) const{
        int p=turn(arr[id].A,arr[id].B,arr[o.id].A);
        int q=turn(arr[id].A,arr[id].B,arr[o.id].B);
        int r=turn(arr[o.id].A,arr[o.id].B,arr[id].A);
        int s=turn(arr[o.id].A,arr[o.id].B,arr[id].B);
        return (p==-1 && q==-1) || (r==1 && s==1);
    }
};

int n;
vector<ev> v;
bool ans[MAXN];
set<cmp> s;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        pnt A=pnt(c,b);
        pnt B=pnt(a,d);
        arr[i]=seg(A,B);
        v.push_back(ev(A,B,0,i));
        v.push_back(ev(B,A,1,i));
    }

    sort(v.begin(),v.end());

    for(ev i: v){
        
        if(i.t==0){
            s.insert(cmp(i.id));
        }
        else{
            s.erase(cmp(i.id));
        }

        if(!s.empty()){
            ans[s.begin()->id]=1;
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++){cnt+=ans[i];}
    cout << cnt << '\n';
    for(int i=1; i<=n;i++){
        if(ans[i]) cout << i << ' ';
    }
    cout << endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted6ms8084 KiB
2Accepted17ms11000 KiB
subtask215/15
3Accepted4ms8356 KiB
4Accepted6ms8692 KiB
5Accepted9ms9852 KiB
6Accepted16ms11512 KiB
7Accepted14ms11780 KiB
subtask315/15
8Accepted4ms9088 KiB
9Accepted4ms9268 KiB
10Accepted4ms9304 KiB
11Accepted4ms9316 KiB
12Accepted4ms9516 KiB
subtask420/20
13Accepted6ms9548 KiB
14Accepted7ms9756 KiB
15Accepted10ms10724 KiB
16Accepted14ms11172 KiB
17Accepted14ms11388 KiB
subtask550/50
18Accepted28ms15604 KiB
19Accepted37ms16312 KiB
20Accepted76ms22592 KiB
21Accepted145ms35388 KiB
22Accepted167ms38456 KiB