Mai intai trebuie sa te autentifici.
Cod sursa(job #164941)
Utilizator | Data | 24 martie 2008 23:06:02 | |
---|---|---|---|
Problema | Popandai | Scor | 8 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.97 kb |
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N_MAX = 310;
int N;
int sub[N_MAX][N_MAX], used[N_MAX];
pair <int, int> v[N_MAX];
double over[N_MAX], under[N_MAX];
int semn(int a, int b, int c)
{
int x = v[a].first, y = v[a].second, x1 = v[b].first, y1 = v[b].second, x2 = v[c].first, y2 = v[c].second;
return (x * (y1 - y2) - y * (x1 - x2) + (x1 * y2) - (y1 * x2));
}
double mabs(double a)
{
return (a < 0 ? -a : a);
}
double arie(int a, int b, int c)
{
return (mabs(0.5 * semn(a, b, c)));
}
void preproc()
{
for (int i = 1; i < N; i ++) {
for (int j = i + 1; j <= N; j ++) {
for (int k = 1; k <= N; k ++) {
if (v[i].first <= v[k].first && v[k].first <= v[j].first && semn(k, i, j) < 0) sub[i][j] ++;
}
}
}
}
int calc(int i, int j, int k)
{
int nrpct;
if (k <= i) {
nrpct = sub[k][j] - sub[k][i] - sub[i][j] - 1;
if (used[i]) nrpct ++;
return nrpct;
}
if (i <= k && k <= j) {
nrpct = sub[i][k] + sub[k][j] - sub[i][j];
if (used[k]) nrpct --;
return nrpct;
}
nrpct = sub[i][k] - sub[i][j] - sub[j][k] - 1;
if (used[j]) nrpct ++;
return nrpct;
}
int calc2(int i, int j, int k)
{
int nrpct;
if (k <= i) {
nrpct = sub[k][i] + sub[i][j] - sub[k][j];
if (used[i]) nrpct --;
return nrpct;
}
if (i <= k && k <= j) {
nrpct = sub[i][j] - sub[i][k] - sub[k][j] - 1;
if (used[k]) nrpct ++;
}
nrpct = sub[i][j] + sub[j][k] - sub[i][k];
if (used[j]) nrpct --;
return nrpct;
}
int main()
{
freopen("popandai.in", "r", stdin);
#ifndef _SCREEN_
freopen("popandai.out", "w", stdout);
#endif
int K, x, y;
scanf("%d %d\n", &N, &K);
for (int i = 1; i <= N; i ++) {
scanf("%d %d\n", &x, &y);
v[i] = make_pair(x, y);
}
sort(v + 1, v + N + 1);
preproc();
pair <int, int> A, B;
double ar;
int nrpct;
for (int i = 1; i <= N; i ++) {
for (int j = i + 1; j <= N; j ++) {
sub[j][i] = sub[i][j];
}
}
for (int i = 1; i <= N; i ++) {
for (int j = 1; j <= N; j ++) {
if (i != j && v[i].first == v[j].first && v[j].second < v[i].second) used[i] = 1;
}
}
double MINN = -1, MIN;
for (int i = 1; i < N - 1; i ++) {
for (int j = i + 1; j <= N; j ++) {
for (int k = 0; k <= N; k ++) over[k] = -1, under[k] = -1;
for (int k = 1; k <= N; k ++) {
if (k != i && k != j) {
ar = arie(i, j, k);
if (semn(k, i, j) > 0) {
nrpct = calc(i, j, k);
if (used[k]) nrpct --;
if (ar < over[nrpct] || over[nrpct] == -1) over[nrpct] = ar;
} else {
nrpct = calc2(i, j, k);
if (used[k]) nrpct ++;
if (ar < under[nrpct] || under[nrpct] == -1) under[nrpct] = ar;
}
}
}
MIN = -1;
for (int KK = K; KK <= N - 3; KK ++) {
for (int x = 0; x <= KK; x ++) {
if (over[x] != -1 && under[KK - x] != -1 && (over[x] + under[KK - x] < MIN || MIN == -1)) {
MIN = over[x] + under[KK - x];
}
}
}
// printf("!!%d %d %0.1lf\n", i, j, MIN);
if (MIN != -1 && (MIN < MINN || MINN == -1)) MINN = MIN;
}
}
printf("%0.1lf\n", MINN);
return 0;
}