10704 2024. 04. 10 09:00:21 Vkrisztian01 Házak cpp17 Időlimit túllépés 0/100 400ms 19400 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Időlimit túllépés 372ms 2428 KiB
subtask2 0/15
3 Hibás válasz 3ms 2536 KiB
4 Hibás válasz 25ms 2768 KiB
5 Időlimit túllépés 400ms 2648 KiB
6 Időlimit túllépés 354ms 3628 KiB
7 Időlimit túllépés 365ms 4276 KiB
subtask3 0/15
8 Elfogadva 3ms 4284 KiB
9 Hibás válasz 4ms 4336 KiB
10 Hibás válasz 4ms 4356 KiB
11 Hibás válasz 8ms 4340 KiB
12 Hibás válasz 19ms 4672 KiB
subtask4 0/20
13 Hibás válasz 25ms 4888 KiB
14 Hibás válasz 94ms 5136 KiB
15 Időlimit túllépés 333ms 4840 KiB
16 Időlimit túllépés 381ms 5312 KiB
17 Időlimit túllépés 370ms 5660 KiB
subtask5 0/50
18 Időlimit túllépés 330ms 6896 KiB
19 Időlimit túllépés 361ms 8156 KiB
20 Időlimit túllépés 361ms 10560 KiB
21 Időlimit túllépés 377ms 16368 KiB
22 Időlimit túllépés 347ms 19400 KiB