#include #include #include #include #include #include #include #include #include #include #include using namespace std; template struct point{ T x, y; }; //judge if line AB intersects line CD template bool intersect(point &a, point &b, point &c, point &d){ bool ans = 1; T s, t; s = (a.x - b.x) * (c.y - a.y) - (a.y - b.y) * (c.x - a.x); t = (a.x - b.x) * (d.y - a.y) - (a.y - b.y) * (d.x - a.x); if (s*t > 0) ans = 0; s = (c.x - d.x) * (a.y - c.y) - (c.y - d.y) * (a.x - c.x); t = (c.x - d.x) * (b.y - c.y) - (c.y - d.y) * (b.x - c.x); if (s*t > 0) ans = 0; return ans; } int main(){ long long N, mx=0, M, cnt, dx, dy; cin >> N; point e1, e2; vector> c(N), d(N), e(2*N); for (int i=0; i> c[i].x >> c[i].y >> d[i].x >> d[i].y; e[i*2] = c[i]; e[i*2+1] = d[i]; } for (int i=0; i