제출 #26624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26624		model_code	무제 (POI11_wyk)	C++14	52 / 100	30000 ms	10508 KiB

Main

/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Wykres                                           *
 *   Autor:             Filip Wolski                                     *
 *   Opis:              Rozwiazanie powolne                              *
 *                      kolo pokrywajace O(n^4),                         *
 *                      wyszukiwanie przyrostowe                         *
 *                                                                       *
 *************************************************************************/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>

#define RMIN 0
#define RMAX 1420000

#define MXN 100000
#define MXM 100000
#define EPS 1e-6

using namespace std;

typedef long double LD;

struct wsp_t {
	LD x, y;
	wsp_t(LD _x = 0., LD _y = 0.) : x(_x), y(_y) { }
};

inline LD sqr(LD x) { return x*x; }

bool LineCrossPoint(wsp_t p1, wsp_t p2, wsp_t l1, wsp_t l2, LD &x, LD &y){
	LD t = (p1.x - p2.x) * (l1.y - l2.y) - (p1.y - p2.y) * (l1.x - l2.x);
	LD s = (l2.x - p2.x) * (l1.y - l2.y) - (l2.y - p2.y) * (l1.x - l2.x);
	if (fabs(t) < EPS) return false;
	x = (s/t) * p1.x + (1-s/t) * p2.x;
	y = (s/t) * p1.y + (1-s/t) * p2.y;
	return true;
}

bool ThreePointCircle(wsp_t p1, wsp_t p2, wsp_t p3, LD &x, LD &y) {
	if (!LineCrossPoint(
				wsp_t((p1.x+p2.x)/2.0,(p1.y+p2.y)/2.0),
				wsp_t((p1.x+p2.x)/2.0+p2.y-p1.y,(p1.y+p2.y)/2.0+p1.x-p2.x),
				wsp_t((p1.x+p3.x)/2.0,(p1.y+p3.y)/2.0),
				wsp_t((p1.x+p3.x)/2.0+p3.y-p1.y,(p1.y+p3.y)/2.0+p1.x-p3.x), x, y)) {
		return false;
	}
	return true;
}

wsp_t wsp[MXN];

bool check_fit(int pc, int kn, LD x, LD y, LD r) {
	for (int i = pc; i <= kn; ++i) {
		LD dist = sqrt(sqr(wsp[i].x - x) + sqr(wsp[i].y - y));
		if (dist > r + EPS) {
			return false;
		}
	}
	return true;
}

bool can_hold(int pc, int kn, LD r, wsp_t &mid) {
	if (pc == kn) {
		mid = wsp[pc];
		return true;
	}
	for (int i = pc; i <= kn; ++i) {
		for (int j = pc; j < i; ++j) {
			LD x = (wsp[i].x + wsp[j].x) / 2.;
			LD y = (wsp[i].y + wsp[j].y) / 2.;
			if (check_fit(pc, kn, x, y, r)) {
				mid.x = x; mid.y = y;
				return true;
			}
			for (int k = pc; k < j; ++k) {
				if (ThreePointCircle(wsp[i], wsp[j], wsp[k], x, y) && check_fit(pc, kn, x, y, r)) {
					mid.x = x; mid.y = y;
					return true;
				}
			}
		}
	}
	return false;
}

int n;

void check(int &pos, LD r, wsp_t &mid) {
	int next = pos+1;
	mid.x = wsp[pos].x;
	mid.y = wsp[pos].y;
	while (next < n && can_hold(pos, next, r, mid)) {
		++next;
	}
	pos = next;
}

wsp_t mid[MXM], midsol[MXM];
int m, s, ssol;

int main() {
	LD rmin = RMIN;
	LD rmax = RMAX;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		scanf("%Lf%Lf", &wsp[i].x, &wsp[i].y);
	}
	ssol = -1;
	while (rmin + EPS < rmax) {
		LD r = (rmin + rmax) / 2.;
		int cnt = 0;
		for (s = 0; s < m && cnt < n; ++s) {
			check(cnt, r, mid[s]);
		}
		if (cnt == n) {
			ssol = s;
			copy(mid, mid+s, midsol);
			rmax = r;
		} else {
			rmin = r;
		}
	}
	assert(ssol != -1 && ssol <= m);
	printf("%.8Lf\n%d\n", rmax, ssol);
	for (int i = 0; i < ssol; ++i) {
		printf("%.8Lf %.8Lf\n", midsol[i].x, midsol[i].y);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

wyk.cpp: In function 'int main()':
wyk.cpp:111:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
wyk.cpp:113:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%Lf%Lf", &wsp[i].x, &wsp[i].y);
                                        ^

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8