10764 2024. 04. 11 14:51:47 EsVagy Házak cpp17 Hibás válasz 30/100 145ms 22912 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <queue>
#include <fstream>
#include <sstream>
#include <math.h>
#include <list>

using namespace std;

using ll = long long;

class vect
{
public:
    ll x;
    ll y;

    vect()
    {
    }

    vect(ll xCoord, ll yCoord) : x(xCoord), y(yCoord)
    {
    }

    vect operator+(vect a)
    {
        return vect(x + a.x, y + a.y);
    }

    vect operator-(vect a)
    {
        return vect(a.x - x, a.y - y);
    }

    int turn(vect a)
    {
        ll turn = x * a.y - a.x * y;
        if (turn == 0)
        {
            return 0;
        }
        return turn > 0 ? 1 : -1;
    }
};

bool between(ll a, ll b, ll c)
{
    return (a >= c && b <= c) || (b >= c && a <= c);
}

class segment
{
public:
    vect a;
    vect b;

    int turn(vect p)
    {
        vect v = b - a;
        vect w = p - a;
        return (v.turn(w));
    }

    bool contains(vect p)
    {
        return turn(p) == 0 && between(a.x, b.x, p.x) && between(a.y, b.y, p.y);
    }

    bool intercept(segment l)
    {
        int turnA = turn(l.a);
        int turnB = turn(l.b);
        int turnC = l.turn(a);
        int turnD = l.turn(b);

        if (turnA == 0 || turnB == 0 || turnC == 0 || turnD == 0)
        {
            return contains(l.a) || contains(l.b) || l.contains(a) || l.contains(b);
        }

        return (turnA != turnB) && (turnC != turnD);
    }
};

bool segment_compare(segment a, segment b) {
    return a.turn(b.a) < 0;
}

bool vect_compare(vect a, vect b) {
    int turn = a.turn(b);

    return turn == 1 || (turn == 0 && a.x + a.y < b.x + b.y);
}

struct point {
    vect v;
    ll segment_index;
    bool end;
};

bool point_compare(point a, point b) {
    int turn = a.v.turn(b.v);
    if (turn != 0) {
        return turn == 1;
    }
    if (a.end != b.end) {
        return a.end > b.end;
    }
    return a.v.x + a.v.y < b.v.x + b.v.y;
}

struct indexedSegment {
    segment s;
    ll i;
    
    bool operator<(const indexedSegment& a) const {
        return segment_compare(this->s, a.s);
    }
};

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

    ll size;
    cin >> size;
    vector<segment> segments(size);
    vector<point> points(size * 2);
    for (ll i = 0; i < size; i++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        vect s {x2, y1};
        vect e {x1, y2};
        segments[i] = segment {s, e};
        points[2*i] = point {s, i, false};
        points[2*i+1] = point {e, i, true};
    }
    
    sort(points.begin(), points.end(), point_compare); 
    set<ll> ans;
    set<indexedSegment> segset;
    for (ll index = 0; index < points.size(); index++) {
        point p = points[index];
        if (!p.end) {
            segset.insert(indexedSegment {segments[p.segment_index], p.segment_index});
        }
        else {
            segset.erase(indexedSegment {segments[p.segment_index], p.segment_index});
        }
        if (index < points.size() - 1 && p.v.turn(points[index + 1].v) == 0) {
            continue;
        }
        if (!segset.empty()) {
            ans.insert(segset.begin()->i);
        }
    }

    cout << ans.size() << "\n";
    for (ll i : ans) {
        cout << i + 1 << " ";
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1704 KiB
2 Elfogadva 14ms 3772 KiB
subtask2 15/15
3 Elfogadva 3ms 2148 KiB
4 Elfogadva 4ms 2420 KiB
5 Elfogadva 8ms 3248 KiB
6 Elfogadva 16ms 4912 KiB
7 Elfogadva 16ms 5104 KiB
subtask3 15/15
8 Elfogadva 3ms 2668 KiB
9 Elfogadva 3ms 2936 KiB
10 Elfogadva 3ms 3172 KiB
11 Elfogadva 3ms 3296 KiB
12 Elfogadva 4ms 3284 KiB
subtask4 0/20
13 Elfogadva 3ms 3108 KiB
14 Hibás válasz 4ms 3328 KiB
15 Elfogadva 9ms 4336 KiB
16 Elfogadva 12ms 4336 KiB
17 Elfogadva 12ms 4336 KiB
subtask5 0/50
18 Hibás válasz 28ms 6676 KiB
19 Elfogadva 43ms 10008 KiB
20 Elfogadva 68ms 12680 KiB
21 Elfogadva 145ms 22912 KiB
22 Hibás válasz 145ms 22216 KiB