1305 2022. 04. 15 12:46:33 k_balint Házak cpp14 Elfogadva 100/100 167ms 38456 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 6ms 8084 KiB
2 Elfogadva 17ms 11000 KiB
subtask2 15/15
3 Elfogadva 4ms 8356 KiB
4 Elfogadva 6ms 8692 KiB
5 Elfogadva 9ms 9852 KiB
6 Elfogadva 16ms 11512 KiB
7 Elfogadva 14ms 11780 KiB
subtask3 15/15
8 Elfogadva 4ms 9088 KiB
9 Elfogadva 4ms 9268 KiB
10 Elfogadva 4ms 9304 KiB
11 Elfogadva 4ms 9316 KiB
12 Elfogadva 4ms 9516 KiB
subtask4 20/20
13 Elfogadva 6ms 9548 KiB
14 Elfogadva 7ms 9756 KiB
15 Elfogadva 10ms 10724 KiB
16 Elfogadva 14ms 11172 KiB
17 Elfogadva 14ms 11388 KiB
subtask5 50/50
18 Elfogadva 28ms 15604 KiB
19 Elfogadva 37ms 16312 KiB
20 Elfogadva 76ms 22592 KiB
21 Elfogadva 145ms 35388 KiB
22 Elfogadva 167ms 38456 KiB