結果

問題 No.869 ふたつの距離
ユーザー e869120e869120
提出日時 2019-08-15 16:16:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,867 bytes
コンパイル時間 851 ms
コンパイル使用メモリ 85,704 KB
実行使用メモリ 36,820 KB
最終ジャッジ日時 2024-09-19 15:32:26
合計ジャッジ時間 30,583 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47 WA * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

bool check(int N, int A, int B, vector<pair<long double, long double>> E) {
	if (E.size() != N) return false;

	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < E.size(); i++) {
		for (int j = i + 1; j < E.size(); j++) {
			long double v = (E[i].first - E[j].first)*(E[i].first - E[j].first) + (E[i].second - E[j].second)*(E[i].second - E[j].second);
			if (v <= 100.0L) cnt1++;
			if (v <= 400.0L) cnt2++;
		}
	}
	if (cnt1 != A) return false;
	if (cnt2 != B) return false;
	return true;
}

vector<long double> construct(int P, int N, int ty) {
	if (P == 0) return vector<long double>{};

	vector<long double> V;
	long double ZA = N * N;
	for (int i = 0; i < P - 1; i++) {
		long double ZZ = 1.0L * i - 1.0L * (P - 2) / 2.0L; ZZ -= 0.314159265358979L;
		V.push_back(abs(ZZ) / ZA);
	}

	vector<long double>Z;
	for (int i = 0; i < P; i++) {
		long double sum = 0;
		for (int j = i + 1; j < P; j++) {
			sum += V[j - 1] * j;
			Z.push_back(1.0L * (10.0L - sum) / (j - i));
		}
	}
	sort(Z.begin(), Z.end());
	reverse(Z.begin(), Z.end());

	long double r = 0;
	if (N == 0) {
		if (ty == 1) r = 30.0L;
		if (ty == 2) r = 40.0L;
	}
	else if (N < Z.size()) {
		if (ty == 1) r = (2.0L * Z[N - 1] + 1.0L * Z[N]) / 3.0L;
		if (ty == 2) r = (1.0L * Z[N - 1] + 2.0L * Z[N]) / 3.0L;
	}
	else {
		if (ty == 1) r = 1e-4;
		if (ty == 2) r = 2e-4;
	}

	vector<long double>A; A.push_back(0);
	for (int i = 1; i < P; i++) {
		A.push_back(A[A.size() - 1] + r + V[i - 1] * i);
	}
	return A;
}

vector<pair<long double, long double>> solve(int N, int A, int B) {
	vector<long double>E1, E2;
	for (int i = N / 2; i <= N; i++) {
		int Z1 = i, Z2 = N - i;
		int S1 = Z1 * (Z1 - 1) / 2, S2 = Z2 * (Z2 - 1) / 2;
		int S = S1 + S2;
		if (S >= A) {
			int parity1 = A * S1 / (S1 + S2);
			int parity2 = A - parity1;
			E1 = construct(Z1, parity1, 1);
			E2 = construct(Z2, parity2, 2);
			break;
		}
	}

	vector<long double> T;
	for (int i = 0; i < E1.size(); i++) {
		for (int j = 0; j < E2.size(); j++) {
			long double V = 400.0L - (E1[i] - E2[j]) * (E1[i] - E2[j]);
			V = sqrtl(V);
			T.push_back(V);
		}
	}
	sort(T.begin(), T.end());
	reverse(T.begin(), T.end());

	int rem = B - (E1.size() * (E1.size() - 1) / 2) - (E2.size() * (E2.size() - 1) / 2);
	long double ret = 2.0;
	if (rem == 0) ret = 30.0L;
	else if (rem < T.size()) ret = (T[rem - 1] + T[rem]) / 2.0L;
	else ret = 10.1L;

	vector<pair<long double, long double>>ans;
	for (int i = 0; i < E1.size(); i++) ans.push_back(make_pair(0.0L, E1[i]));
	for (int i = 0; i < E2.size(); i++) ans.push_back(make_pair(ret, E2[i]));
	return ans;
}

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	vector<pair<long double, long double>> D = solve(N, A, B);
	for (int i = 0; i < N; i++) printf("%.12Lf %.12Lf\n", D[i].first, D[i].second);
	return 0;
}
0