/// https://cses.fi/problemset/task/2192/ #include using namespace std; const long long INF = 3e9; struct P{ long long x, y; void read(){cin>>x>>y;}; P operator - (P b) { return {x-b.x,y-b.y}; } void operator -= (P b) { x -= b.x; y -= b.y; } long long operator * (P b) { return (1LL*x*b.y) - (1LL*y*b.x) ; } long long triangle (P b , P c) { return (b - *this) * (c - *this); } }v[1001]; bool intersectSegment(P p1, P p2, P p3, P p4) { /// If parrallel if((p2-p1) * (p4-p3) == 0) { if(p1.triangle(p2,p3) != 0) return false; for(int i = 1;i<=2;i++) { if((max(p1.x,p2.x) < min(p3.x,p4.x)) || (max(p1.y,p2.y) < min(p3.y,p4.y))) return false; swap(p1,p3); swap(p2,p4); } return true; } ///Not parrallel for(int i = 1;i<=2;i++) { long long sign1 = p1.triangle(p2,p3); long long sign2 = p1.triangle(p2,p4); if((sign1<0&&sign2<0) || (sign1>0&&sign2>0)) return false; swap(p1,p3); swap(p2,p4); } return true; } bool segment_contains(P a, P b, P c) { if(a.triangle(b,c) != 0) return false; return (min(a.x,b.x) <= c.x && c.x <= max(a.x,b.x)) && (min(a.y,b.y) <= c.y && c.y <= max(a.y,b.y)) ; } int main() { int n , m ; cin>>n>>m; for(int i = 0;i