Submission #1371765

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define OUT(x) cout << #x << " = " << x << endl
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }
long long lin() { long long x; scanf("%lld", &x); return x; }

int V;
vector<int> g[30][20202];
vector<int> rg[30][20202];
vector<int> order[30];
bool used[30][20202];
int cmp[30][20202];

int cnt = 0;

int n;
vector<int> x, y;

void add_edge(int from, int to) {
        g[cnt][from].push_back(to);
        rg[cnt][to].push_back(from);
}
void dfs(int v) {
        used[cnt][v] = true;
        for (auto i : g[cnt][v]) if (!used[cnt][i]) dfs(i);
        order[cnt].push_back(v);
}
void rdfs(int v, int k) {
        used[cnt][v] = true;
        cmp[cnt][v] = k;
        for (auto i : rg[cnt][v]) if (!used[cnt][i]) rdfs(i, k);
}
int StronglyConnectedComponent() {
        memset(used[cnt], 0, sizeof(used[cnt]));
        order[cnt].clear();
        for (int i = 0; i < V; i ++) if (!used[cnt][i]) dfs(i);
        memset(used[cnt], 0, sizeof(used[cnt]));
        int k = 0;
        for (int i = order[cnt].size() - 1; i >= 0; i --) if (!used[cnt][order[cnt][i]]) rdfs(order[cnt][i], k ++);
        return k;
}

bool B(int d) {
        //rep(i, 20202) g[i].clear();
        //rep(i, 20202) rg[i].clear();
        //order.clear();
        //memset(used, 0, sizeof(used));
        //memset(cmp, 0, sizeof(cmp));
        int d1, d2, d3, d4;
        rep(i, n) reu(j, i + 1, n) {
                d1 = abs(x[i] - x[j]);
                d2 = abs(x[i] - y[j]);
                d3 = abs(y[i] - x[j]);
                d4 = abs(y[i] - y[j]);
                if (d1 >= d && d2 >= d && d3 >= d && d4 >= d) continue;
                else if (d1 < d && d2 < d && d3 < d && d4 < d) return false;
                else if (d1 >= d && d2 < d && d3 < d && d4 < d) {
                        add_edge(i + n, i);
                        add_edge(j + n, j);
                }
                else if (d1 < d && d2 >= d && d3 < d && d4 < d) {
                        add_edge(i + n, i);
                        add_edge(j, j + n);
                }
                else if (d1 < d && d2 < d && d3 >= d && d4 < d) {
                        add_edge(i, i + n);
                        add_edge(j + n, j);
                }
                else if (d1 < d && d2 < d && d3 < d && d4 >= d) {
                        add_edge(i, i + n);
                        add_edge(j, j + n);
                }
                else if (d1 >= d && d2 >= d && d3 < d && d4 < d) {
                        add_edge(i + n, i);
                }
                else if (d1 >= d && d2 < d && d3 >= d && d4 < d) {
                        add_edge(j + n, j);
                }
                else if (d1 >= d && d2 < d && d3 < d && d4 >= d) {
                        add_edge(i, j);
                        add_edge(i + n, j + n);
                        //add_edge(j, i);
                        //add_edge(j + n, i + n);
                }
                else if (d1 < d && d2 >= d && d3 >= d && d4 < d) {
                        add_edge(i, j + n);
                        add_edge(i + n, j);
                        //add_edge(j + n, i);
                        //add_edge(j, i + n);
                }
                else if (d1 < d && d2 >= d && d3 < d && d4 >= d) {
                        add_edge(j, j + n);
                }
                else if (d1 < d && d2 < d && d3 >= d && d4 >= d) {
                        add_edge(i, i + n);
                }
                else if (d1 >= d && d2 >= d && d3 >= d && d4 < d) {
                        add_edge(i + n, j);
                        add_edge(j + n, i);
                }
                else if (d1 >= d && d2 >= d && d3 < d && d4 >= d) {
                        add_edge(i + n, j + n);
                        add_edge(j, i);
                }
                else if (d1 >= d && d2 < d && d3 >= d && d4 >= d) {
                        add_edge(i, j);
                        add_edge(j + n, i + n);
                }
                else {
                        add_edge(i, j + n);
                        add_edge(j, i + n);
                }
        }
        StronglyConnectedComponent();
        rep(i, n) if (cmp[cnt][i] == cmp[cnt][i + n]) return false;
        return true;
}

static const int INF = 0x3f3f3f3f;

signed main() { 
        //auto start = chrono::high_resolution_clock::now();
        scanf("%d", &n);
        V = 2 * n;
        x.resize(n), y.resize(n);
        int mi = INF, ma = -1;
        rep(i, n) { 
                scanf("%d%d", &x[i], &y[i]);
                amin(mi, x[i]);
                amin(mi, y[i]);
                amax(ma, x[i]);
                amax(ma, y[i]);
        }
        //vector<int> z;
        //rep(i, n) {
        //        z.push_back(x[i]);
        //        z.push_back(y[i]);
        //}
        //sort(all(z));
        //int r = (z.back() - z.front()) / (n - 1) + 1;
        int r = (ma - mi) / (n - 1) + 1;
        int l = 0;
        //int r = 10e8 / (n - 1);
        while (r - l > 1) {
                int mid = (l + r) / 2;
                //OUT(mid);
                if (B(mid)) l = mid;
                else r = mid;
                cnt ++;
        }
        cout << l << endl;
        //auto end = chrono::high_resolution_clock::now();
        //cout << chrono::duration_cast<chrono::milliseconds>(end - start).count() << " ms" << endl;
        return 0;
}               

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:12:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘long long int lin()’:
./Main.cpp:13:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 long long lin() { long long x; scanf("%lld", &x); return x; }
                                                 ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:131:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &n);
                        ^
./Main.cpp:136:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &x[i], &y[i]);
                         ...

Judge Result