Nu aveti permisiuni pentru a descarca fisierul grader_test11.ok

Cod sursa(job #2011750)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 17 august 2017 02:13:29
Problema Popandai Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("popandai.in");
ofstream fo("popandai.out");

using f64 = double;

const int N = 305;
const f64 SIN = sin(0.1), COS = cos(0.1), EPS = 1e-6;


struct Point {
	f64 x, y;
	
	void rot() {
		f64 tx(x * COS - y * SIN), ty(x * SIN + y * COS);
		x = tx, y = ty; } 

	inline bool operator < (const Point &arg) const {
		return y < arg.y; } };


int boven[N][N];

vector<Point> pts;
vector<f64> up, dn;
f64 ans;
int n, k;


static f64 ccw(const Point &a, const Point &b, const Point &c) {
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x); }

static int in_tri(int a, int b, int c) {
	if (pts[a].x > pts[b].x) swap(a, b);
	if (pts[b].x > pts[c].x) swap(b, c);
	if (pts[a].x > pts[b].x) swap(a, b);
	return abs(boven[a][b] - boven[b][c] - boven[a][c]); }

static f64 area(int a, int b, int c) {
	return abs(ccw(pts[a], pts[b], pts[c]) * 0.5); }


int main() {
	fi >> n >> k;
	pts.resize(n);
	for (auto &i: pts) {
		fi >> i.x >> i.y;
	 	i.rot(); 
	}	

	//sort(begin(pts), end(pts), [&](const Point &a, const Point &b) {
	//	return a.y < b.y; });


	for (int i = 0; i < n; ++i)
	for (int j = i + 1; j < n; ++j) {
		f64 a, b, st, dr;

		a = (pts[i].y - pts[j].y) / (pts[i].x - pts[j].x);
		b = pts[i].y - pts[i].x * a;

		st = min(pts[i].x, pts[j].x) - EPS;
		dr = max(pts[i].x, pts[j].x) + EPS;

		for (int k = 0; k < n; ++k) if (st < pts[k].x && pts[k].x < dr && pts[k].x * a + b + EPS < pts[k].y)
			++boven[i][j];
		boven[j][i] = boven[i][j]; }

	up.resize(n + 1);
	dn.resize(n + 1);

	ans = 1e9;
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j) {
			fill(begin(up), end(up), 1e9);
			fill(begin(dn), end(dn), 1e9); 

			for (int k = 0; k < n; ++k) if (k != i && k != j) {
				if (ccw(pts[i], pts[j], pts[k]) > 0)
					up[in_tri(i, j, k)] = min(up[in_tri(i, j, k)], area(i, j, k));
				else
					dn[in_tri(i, j, k)] = min(dn[in_tri(i, j, k)], area(i, j, k)); }

			for (int l = 0; l <= k; ++l) 
				ans = min(ans, up[l] + dn[k - l]); }


	fo << setprecision(1) << fixed;
	fo << ans << endl;

	return 0; }