Submission #79952

#	Time	Username	Problem	Language	Result	Execution time	Memory
79952		bash	Park (BOI16_park)	C++17	0 / 100	761 ms	85332 KiB

park

/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back

#define int __int64_t


const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;
using namespace std;

typedef long long ll;

long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}


const double eps = 1e-9;

bool equalTo ( double a, double b ){ if ( fabs ( a - b ) <= eps ) return true; else return false; }
bool notEqual ( double a, double b ){if ( fabs ( a - b ) > eps ) return true; else return false; }
bool lessThan ( double a, double b ){ if ( a + eps < b ) return true; else return false; }
bool lessThanEqual ( double a, double b ){if ( a < b + eps ) return true;   else return false;}
bool greaterThan ( double a, double b ){if ( a > b + eps ) return true;else return false;}
bool greaterThanEqual ( double a, double b ){if ( a + eps > b ) return true;else return false;}


const int N = 2222;


struct edge{
	int s, e, x;
};
vector<edge> v;
vector <int> g[N];

double ans[N][N];
double d[N][N];
int par[N];
int G[N][N];

struct Point {
	double x, y, r;
};

Point a[N];
double dist(int i, int j) {
	double X = (a[i].x - a[j].x);
	double Y = (a[i].y - a[j].y);
	return sqrt(X*X+Y*Y);
} 
                                                       
bool cmp(edge a, edge b) {
	return a.x < b.x;
}


int Find(int v) {
	return par[v] = (par[v] == v ? v : Find(par[v]));
}

bool uni(int p, int q){
	p = Find(p), q = Find(q);
	if (p == q) return 0;
	par[q] = p; return 1;
}


void dfs(int v, int p, int s, int D) {
	d[s][v] = D;
	for (int i : g[v]) {
		if (i != p) {
			dfs(i, v, s, max(D, G[v][i]));
		}
	}
}

main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    int n = readInt(), m = readInt();
    int w = readInt(), h = readInt();
    for (int i = 1; i <= n+4; i++) {
    	par[i] = i;
    }
    for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y >> a[i].r;
    }
    for (int i = 1; i <= n; i++) {
    	for (int j = 1;  j<= n; j++) {
    		if (i == j) continue;
    		double Z = dist(i, j) - (a[i].r + a[j].r);
    		G[i][j] = G[j][i] = (int)floor(Z / 2 + eps);
    	}
    }
    for (int i = 1; i <= n; i++) {
		G[i][n+1] = G[n+1][i] = (a[i].y - a[i].r) / 2;
		G[i][n+2] = G[n+2][i] = (a[i].x - a[i].r) / 2;
		G[i][n+3] = G[n+3][i] = (w - a[i].r - a[i].x) / 2;
		G[i][n+4] = G[n+4][i] = (h - a[i].r - a[i].y) / 2;
    }
    for (int i = 1; i <= 4; i++) {
    	for (int j = 1; j <= 4; j++) {
    		if (i != j) G[n+i][n+j] = MOD;
    	}
    }
    for(int i = 1; i<=n+4; i++){
		for(int j = 1; j < i; j++){
			v.push_back({i, j, G[i][j]});
		}
	}
	sort(v.begin(), v.end(), cmp);
	for (auto &i : v) {
		if (uni(i.s, i.e)) {
			g[i.s].pb(i.e);
			g[i.e].pb(i.s);
		}
	}
	for (int i = n + 1; i <= n + 4; i++) {
		dfs(i, 0, i, 0);			
	}
	ans[0][0] = ans[1][1] = ans[2][2] = ans[3][3] = 1e9;
	ans[0][1] = ans[1][0] = min(d[n+1][n+2], min(d[n+1][n+3], d[n+1][n+4]));
	ans[0][2] = ans[2][0] = min(min(d[n+1][n+2], d[n+1][n+4]), min(d[n+3][n+4], d[n+3][n+4]));
	ans[0][3] = ans[3][0] = min(d[n+2][n+1], min(d[n+2][n+3], d[n+2][n+4]));
	ans[1][2] = ans[2][1] = min(d[n+3][n+1], min(d[n+3][n+2], d[n+3][n+4]));
	ans[1][3] = ans[3][1] = min(min(d [n+1][n+3], d[n+1][n+4]), min(d[n+2][n+3], d[n+2][n+4]));
	ans[2][3] = ans[3][2] = min(d[n+4][n+1], min(d[n+4][n+2], d[n+4][n+3]));

	while(m--) {
    	int r = readInt(), e = readInt();
		for(int i = 1; i <= 4; i++){
			if(ans[e-1][i-1] >= r){
				putchar(i + '0');
			}
		}
		puts("");
    }
    return 0;
}

Compilation message (stderr)

park.cpp:124:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42