Cod sursa(job #1765574)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 26 septembrie 2016 20:48:17
Problema Popandai Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 350

using namespace std;

struct coord
{
    int x, y;
    coord(int x = 0, int y = 0) : x(x), y(y) { }
    bool operator()(const coord &e, const coord &f)
    {
        if (e.x != f.x) return e.x < f.x;
        return e.y < f.y;
    }
};
int n, k;
coord a[MAXN];
int sub[MAXN][MAXN];
double ar[MAXN];

void citire()
{
	scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
		scanf("%d %d", &a[i].x, &a[i].y);
}

double det(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1*y3;
}

double det(coord e, coord f, coord g)
{
    return det(e.x, e.y, f.x, f.y, g.x, g.y);
}

void prepare()
{
	sort(a+1, a+n+1, coord());
	for (int i = 1; i <= n; i++)
		for (int j = i+1; j <= n; j++)
			for (int k = i+1; k < j; k++)
                if (det(a[i], a[j], a[k]) < 0)
					sub[i][j]++, sub[j][i]++;

}

int triunghi(int e, int f, int g)
{
    int cs[3] = {e, f, g};
    sort(cs, cs+3, coord);

    if (det(a[cs[0]], a[cs[1]], a[cs[2]]) > 0) {
        return sub[cs[0]][cs[2]] - sub[cs[0]][cs[1]] - sub[cs[1]][cs[2]] - 1;
    }
    else {
        return sub[cs[0]][cs[1]] + sub[cs[1]][cs[2]] - sub[cs[0]][cs[2]];
    }
}
double myabs(double x)
{
	if (x < 0) return -x;
	return x;
}
void solve()
{
	double rez = 5e100;
    for (int i = 1; i <= n; i++) {
		for (int j = i+1; j <= n; j++) {
			for (int k = 0; k <= n; k++)
				ar[k] = 5e100;
            for (int k = 1; k <= n; k++) {
				if (k == i || k == j) continue;
				if (det(a[i], a[j], a[k]) > 0) continue;
				int pts = triunghi(i, j, k);
                ar[pts] = min(ar[pts], myabs(det(a[i], a[j], a[k])));
            }
            for (int k = n-1; k >= 0; k--)
				ar[k] = min(ar[k], ar[k+1]);
            for (int ki = 1; ki <= n; ki++) {
				if (ki == i || ki == j) continue;
				if (det(a[i], a[j], a[ki]) < 0) continue;
				int pts = triunghi(i, j, ki);
				rez = min(rez,  ar[k-pts] + myabs(det(a[i], a[j], a[ki])));
            }
		}
    }
    printf("%.1lf", rez/2);
}

int main()
{
    freopen("popandai.in", "r", stdin);
    freopen("popandai.out", "w", stdout);

    citire();
    prepare();
	solve();

    return 0;
}