Участник:Taranov srg/Ant

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ANTTT

C++ 14 (clang 8.0)

#include <cmath>
#include <fstream>
#include <iostream>
 
using namespace std;
 
const int MAX = 1001;
 
struct Point{
    int x, y;
};
 
struct Segment{
    Point a, b;
};
 
Segment seg[MAX];
int component_index[MAX];
 
int find(int u) {
    if (u!=component_index[u]) component_index[u] = find(component_index[u]);
    return component_index[u];
}
 
inline void unite(int u, int v) {
    component_index[u] = component_index[v];
}
 
inline int direction(Point &pi, Point &pj, Point &pk) {
    return (pk.x-pi.x)*(pj.y-pi.y)-(pj.x-pi.x)*(pk.y-pi.y);
}
 
inline bool on_segment(Point &pi, Point &pj, Point &pk) {
    return (min(pi.x,pj.x) <=  pk.x) && (pk.x <= max(pi.x,pj.x)) && (min(pi.y,pj.y) <= pk.y) && (pk.y <= max(pi.y,pj.y));
}
 
inline bool intersect(Point &p1, Point &p2, Point &p3, Point &p4) {
    int d1, d2, d3, d4;
    d1 = direction(p3, p4, p1);
    d2 = direction(p3, p4, p2);
    d3 = direction(p1, p2, p3);
    d4 = direction(p1, p2, p4);
    if (((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) return true;
    if (!d1 && on_segment(p3, p4, p1)) return true;
    if (!d2 && on_segment(p3, p4, p2)) return true;
    if (!d3 && on_segment(p1, p2, p3)) return true;
    if (!d4 && on_segment(p1, p2, p4)) return true;
    return false;
}
 
int main() {
    int t, m, n, i, j, k, c1, c2, a, b;
    scanf("%d", &t);
    for ( i=0; i<t; ++i) {
        scanf("%d%d", &n, &m);
        for (j = 1; j <= n; j++) {
            component_index[j] = j;
            scanf("%d%d%d%d", &seg[j].a.x, &seg[j].a.y, &seg[j].b.x, &seg[j].b.y);
            // input_file >> seg[j].a.x >> seg[j].a.y >> seg[j].b.x >> seg[j].b.y;
        }
 
        for (j=1; j<=n-1; j++) {
            for (k=j+1; k<=n; k++) {
                c1 = find(j);
                c2 = find(k);
                if (c1 != c2 && intersect(seg[j].a, seg[j].b, seg[k].a, seg[k].b)) unite(c1, c2);
            }
        }
        for (j=0; j<m; ++j) {
            scanf("%d%d", &a, &b);
            // input_file >> a >> b;
            c1 = find(a);
            c2 = find(b);
            if (c1==c2) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}