#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<(indexedSegment& a) {
//return segment_compare(this->s, a.s);
int turn = this->s.turn(a.s.a);
if (turn != 0) {
return turn;
}
return this->i < a.i;
}
};
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";
}
exit status 1
In file included from /usr/include/c++/11/string:48,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/ostream:38,
from /usr/include/c++/11/iostream:39,
from main.cpp:1:
/usr/include/c++/11/bits/stl_function.h: In instantiation of 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = indexedSegment]':
/usr/include/c++/11/bits/stl_tree.h:2071:35: required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = indexedSegment; _Val = indexedSegment; _KeyOfValue = std::_Identity<indexedSegment>; _Compare = std::less<indexedSegment>; _Alloc = std::allocator<indexedSegment>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = indexedSegmen...