Pagini recente » Cod sursa (job #758465) | Cod sursa (job #893645) | Profil Liza | Cod sursa (job #1644732) | Cod sursa (job #164807)
Cod sursa(job #164807)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define nm 310
#define xx first
#define yy second
#define inf 1000000000
int n, m, nr[nm][nm];
double sol = inf;
vector< pair<int, int> > v;
inline int abs(int x)
{
if (x < 0)
return -x;
return x;
}
inline int det(int i, int j, int k)
{
return v[i].xx * v[j].yy + v[j].xx * v[k].yy + v[k].xx * v[i].yy - v[i].xx * v[k].yy - v[j].xx * v[i].yy - v[k].xx * v[j].yy;
}
int cate(int i, int j, int k)
{
int rez = 0;
if (v[i].xx * v[j].yy - v[j].xx * v[i].yy > 0)
rez += nr[i][j];
else
rez -= nr[i][j];
if (v[j].xx * v[k].yy - v[k].xx * v[j].yy > 0)
rez += nr[j][k];
else
rez -= nr[j][k];
if (v[k].xx * v[i].yy - v[i].xx * v[k].yy > 0)
rez += nr[k][i];
else
rez -= nr[k][i];
return abs(rez);
}
double arie(int i, int j, int k)
{
return 0.5 * abs(det(i, j, k));
}
int main()
{
freopen("popandai.in", "r", stdin);
freopen("popandai.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
v.push_back(make_pair(x, y));
}
sort(v.begin(), v.end());
/*
for (int i = 0; i < n; ++i)
printf("%d %d\n", v[i].xx, v[i].yy);
*/
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (v[i].xx != v[j].xx) {
int a = v[j].yy - v[i].yy, b = v[i].xx - v[j].xx, c = v[i].yy - a * v[i].xx;
for (int k = 0; k < n; ++k)
if (k != i && k != j)
if (a * v[k].xx + b * v[k].yy + c > 0)
++nr[i][j];
nr[j][i] = nr[i][j];
}
/*
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
printf("%d ", nr[i][j]);
printf("\n");
}
*/
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
int a = v[j].yy - v[i].yy, b = v[i].xx - v[j].xx, c = v[i].yy - a * v[i].xx;
double st = inf, dr = inf;
for (int k = 0; k < n; ++k)
if (k != i && k != j) {
int temp = cate(i, j, k);
double area = arie(i, j, k);
if (a * v[k].xx + b * v[k].yy + c < 0 && temp >= m && area < st)
st = area;
else if (a * v[k].xx + b * v[k].yy + c > 0 && temp >= m && area < dr)
dr = area;
}
if (sol > st + dr)
sol = st + dr;
}
/*
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
for (int k = j + 1; j <= n; ++j)
printf("%d\n", cate(i, j, k));
*/
printf("%.1lf\n", sol);
return 0;
}