Pagini recente » Cod sursa (job #3270802) | Cod sursa (job #617143) | Cod sursa (job #2464476) | Cod sursa (job #1593021) | Cod sursa (job #1171411)
#include <fstream>
#include <algorithm>
#include <utility>
#include <iomanip>
#define point pair<int,int>
#define x first
#define y second
#define maxn 301
#define inf 900000000
using namespace std;
ifstream fin ("popandai.in");
ofstream fout ("popandai.out");
point v[maxn];
int under[maxn][maxn],n,K;
double a1[maxn],a2[maxn],par1[maxn],par2[maxn],ans=inf;
int det (point a, point b, point c)
{
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
double area (point a, point b, point c)
{
double A = det (a,b,c);
if (A < 0)
return -A/2;
return A/2;
}
int main()
{
fin>>n>>K;
for (int i=1; i<=n; ++i)
{
fin>>v[i].x>>v[i].y;
}
sort (v+1,v+n+1);
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(v[i],v[j],v[k]) < 0)
++under[i][j];
}
}
}
for (int i=1; i<=n; ++i)
{
for (int j=i+1; j<=n; ++j)
{
for (int k=0; k<=K; ++k)
{
a1[k] = inf;
a2[k] = inf;
}
for (int k = 1; k<=n; ++k)
{
if (k == i || k == j)
continue;
int ii = i, jj = j, kk = k;
if (kk > jj)
swap (kk,jj);
if (kk < ii)
swap (ii,kk);
double a = area (v[i],v[j],v[k]);
int in = under[ii][kk] + under[kk][jj] - under[ii][jj];
if (in < 0)
in = -in - 1;
if (det(v[i],v[j],v[k]) > 0)
a1[in] = min (a1[in],a);
else a2[in] = min (a2[in],a);
}
par1[K] = a1[K];
par2[K] = a2[K];
for (int k=K-1; k>=0; --k)
{
par1[k] = min (a1[k],par1[k+1]);
par2[k] = min (a2[k],par2[k+1]);
}
for (int k=0; k<=K; ++k)
ans = min (ans,par1[k]+par2[K-k]);
}
}
fout<<fixed<<setprecision(1)<<ans;
}