Submission #100338

#	Time	Username	Problem	Language	Result	Execution time	Memory
100338		rkocharyan	Konj (COCI19_konj)	C++14	70 / 70	118 ms	22976 KiB

konj

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 7;
const int M = 307;
 
struct pt {
    int x, y;
    pt() {}
    pt(int x, int y) : x(x), y(y) {}
};
 
struct line {
    pt a, b;
    line() {}
    line(pt a, pt b) : a(a), b(b) {}
};
 
int n;
bool was[N];
bool vis[M][M];
vector <int> r[M][M];
vector <line> p;
vector <line> comp;
pt t;
 
void dfs(int v) {
    if (was[v]) return;
    was[v] = true;
    line kek = p[v];
    comp.push_back(kek);
    for (int u : r[kek.a.x][kek.a.y]) {
        dfs(u);
    }
    for (int u : r[kek.b.x][kek.b.y]) {
        dfs(u);
    }
}
 
bool contain(line l, pt c) {
    pt a = l.a;
    pt b = l.b;
    if (a.x == b.x) {
        if (a.y > b.y) swap(a, b);
        return c.x == a.x && a.y <= c.y && c.y <= b.y;
    }
    if (a.x > b.x) swap(a, b);
    return c.y == a.y && a.x <= c.x && c.x <= b.x;
}
 
bool ok(line x, line y) {
    return contain(y, x.a) || contain(y, x.b);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        pt a, b;
        cin >> a.x >> a.y;
        cin >> b.x >> b.y;;
        r[a.x][a.y].push_back(i);
        r[b.x][b.y].push_back(i);
        line kek(a, b);
        p.push_back(kek);
    }
    cin >> t.x >> t.y;
    int pos = -1;
    for (int i = 0; i < n; i++) {
        if (contain(p[i], t)) {
            pos = i;
            break;
        }
    }
    if (pos == -1) {
        return 0;
    }
    dfs(pos);
    int mnx = 300, mny = 300;
    int mxx = 0, mxy = 0;
    for (line x : comp) {
        mnx = min(mnx, x.a.x);
        mnx = min(mnx, x.b.x);
        mny = min(mny, x.a.y);
        mny = min(mny, x.b.y);
        mxx = max(mxx, x.a.x);
        mxx = max(mxx, x.b.x);
        mxy = max(mxy, x.a.y);
        mxy = max(mxy, x.b.y);
        pt a = x.a;
        pt b = x.b;
        if (a.x == b.x) {
            if (a.y > b.y) swap(a, b);
            for (int i = a.y; i <= b.y; i++) {
                vis[a.x][i] = true;
            }
        } else {
            if (a.x > b.x) swap(a, b);
            for (int i = a.x; i <= b.x; i++) {
                vis[i][a.y] = true;
            }
        }
    }
    for (int i = mxy; i >= mny; i--) {
        for (int j = mnx; j <= mxx; j++) {
            if (vis[j][i]) cout << '#';
            else cout << '.';
        }
        cout << '\n';
    }
    return 0;
}

• Subtask 1: 70 / 70