Cod sursa(job #2011719)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 16 august 2017 23:25:05
Problema Popandai Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 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;
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() {
	f64 ant, a, b, st, dr;

	fi >> n >> k;
	pts.resize(n);
	for (auto &i: pts)
		fi >> i.x >> i.y, i.rot();
 
	sort(begin(pts), end(pts));
	
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j) {
			a = (pts[i].y - pts[j].y) / (pts[i].x - pts[j].x);
			b = pts[i].y - a * pts[i].x;

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

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

			boven[j][i] = boven[i][j]; }

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

	ant = 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);

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

			for (int k = 0; k < n; ++k) if (k != i && k != j)
				if (a * pts[k].x + b < pts[k].y) 
					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 k = 0; k < n; ++k) {
				if (k > 0)
					 dn[k] = min(dn[k], dn[k - 1]);
				ant = min(ant, up[n - k] + dn[k]); } }
	
	fo << setprecision(1) << fixed;
	fo << ant << endl;

	return 0; }