107042024-04-10 09:00:21Vkrisztian01Házakcpp17Időlimit túllépés 0/100400ms19400 KiB
#include <iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
typedef long long ll;
using ll = long long;

using namespace std;

struct point
{
    ll x;
    ll y;
};


ll n;
point a,b,origo;
vector<pair<point,point> > hazak;
vector<pair<int,int> > polaris;
vector<int>hazrendezett;
vector<int>pontszam;
set<int>latszik;
set<pair<int,int> > akt;

void input()
{
    origo.x=0;
    origo.y=0;
    for(int i=1;i<=n;i++)
    {
        cin>>hazak[i].first.x>>hazak[i].first.y>>hazak[i].second.x>>hazak[i].second.y;
        swap(hazak[i].first.x,hazak[i].second.x);
        polaris.push_back(make_pair(i,1));
        polaris.push_back(make_pair(i,0));
    }
}

int fordul(point a,point b,point c)
{
    ll s=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    if(s<0) return -1;
    if(s==0) return 0;
    if(s>1) return 1;
}

void polaris_rendezes()
{
    for(int i=0;i<2*n;i++)
    {
        for(int j=2*n-1;j>i;j--)
        {
            if(polaris[j].second==1) a=hazak[polaris[j].first].second;
            else a=hazak[polaris[j].first].first;
            if(polaris[j-1].second==1) b=hazak[polaris[j-1].first].second;
            else b=hazak[polaris[j-1].first].first;
            if(fordul(origo,a,b)==1) swap(polaris[j],polaris[j-1]);
        }
    }
}

bool elorebb(int i,int j)
{
    if(fordul(hazak[i].first,hazak[i].second,hazak[j].first)==-1 || fordul(hazak[i].first,hazak[i].second,hazak[j].second)==-1) return true;
    return false;
}

void hazrendezes()
{
    for(int i=1;i<=n;i++) hazrendezett[i]=i;
    for(int i=1;i<n;i++)
    {
        for(int j=n;j>i;j--)
        {
            if(elorebb(hazrendezett[j],hazrendezett[j-1])) swap(hazrendezett[j],hazrendezett[j-1]);
        }
    }
    for(int i=1;i<=n;i++) pontszam[hazrendezett[i]]=i;

}

void sopor()
{
    stack<int>torlendo;
    for(int i=0;i<2*n;i++)
    {
        while(!torlendo.empty())
        {
            akt.erase(make_pair(pontszam[torlendo.top()],torlendo.top()));
            torlendo.pop();
        }
        if(polaris[i].second==0)
        {
            akt.insert(make_pair(pontszam[polaris[i].first],polaris[i].first));
        }
        else torlendo.push(polaris[i].first);
        latszik.insert(akt.begin()->second);

    }
}


int main()
{
    cin>>n;
    hazak.resize(n+1);
    hazrendezett.resize(n+1);
    pontszam.resize(n+1);
    input();
    polaris_rendezes();
    hazrendezes();
    sopor();
    cout<<latszik.size()<<endl;
    for(auto x:latszik) cout<<x<<" ";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Időlimit túllépés372ms2428 KiB
subtask20/15
3Hibás válasz3ms2536 KiB
4Hibás válasz25ms2768 KiB
5Időlimit túllépés400ms2648 KiB
6Időlimit túllépés354ms3628 KiB
7Időlimit túllépés365ms4276 KiB
subtask30/15
8Elfogadva3ms4284 KiB
9Hibás válasz4ms4336 KiB
10Hibás válasz4ms4356 KiB
11Hibás válasz8ms4340 KiB
12Hibás válasz19ms4672 KiB
subtask40/20
13Hibás válasz25ms4888 KiB
14Hibás válasz94ms5136 KiB
15Időlimit túllépés333ms4840 KiB
16Időlimit túllépés381ms5312 KiB
17Időlimit túllépés370ms5660 KiB
subtask50/50
18Időlimit túllépés330ms6896 KiB
19Időlimit túllépés361ms8156 KiB
20Időlimit túllépés361ms10560 KiB
21Időlimit túllépés377ms16368 KiB
22Időlimit túllépés347ms19400 KiB