Pagini recente » Cod sursa (job #804294) | Cod sursa (job #1169037) | Cod sursa (job #1776169) | Cod sursa (job #1177128) | Cod sursa (job #180550)
Cod sursa(job #180550)
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm 301
#define Inf 2000000000
#define point pair<int,int>
#define x first
#define y second
#define min(a,b) ((a)<(b)?(a):(b))
int Sub[Nm][Nm],n,m,ans;
point P[Nm];
void read()
{
int i;
freopen("popandai.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=0;i<n;++i)
scanf("%d%d",&P[i].x,&P[i].y);
}
inline int cross(int i, int j, int k)
{
return (P[j].x-P[i].x)*(P[k].y-P[i].y)-(P[k].x-P[i].x)*(P[j].y-P[i].y);
}
inline int inside(int i, int j, int k)
{
if(P[k].x>P[j].x)
j=j^k, k=j^k, j=j^k;
if(P[k].x<P[i].x)
i=i^k, k=i^k, i=i^k;
if(cross(i,j,k)<0)
return Sub[i][j]-Sub[i][k]-Sub[k][j]-(P[k].x<P[j].x?1:0);
return Sub[i][k]+Sub[k][j]-Sub[i][j]-(P[i].x==P[k].x);
}
void solve()
{
int A[Nm],B[Nm],i,j,k,c,p;
sort(P,P+n);
for(i=0;i<n;++i)
for(j=i+1;j<n;++j)
{
if(P[i].x==P[j].x) continue;
for(k=0;k<n;++k)
if(i!=k && j!=k && P[k].x>=P[i].x && P[k].x<P[j].x && cross(i,j,k)<0)
++Sub[i][j];
Sub[j][i]=Sub[i][j];
}
ans=Inf;
for(i=0;i<n;++i)
for(j=i+1;j<n;++j)
{
for(k=0;k<=m;++k) A[k]=B[k]=Inf;
for(k=0;k<n;++k)
{
if(i==k || j==k) continue;
c=cross(i,j,k);
p=inside(i,j,k);
if(c<0) A[p]=min(A[p],-c);
else B[p]=min(B[p],c);
}
for(k=m-1;k>=0;--k)
A[k]=min(A[k],A[k+1]);
for(k=0;k<=m;++k)
if(B[k]<Inf) ans=min(ans,B[k]+A[m-k]);
}
}
void write()
{
freopen("popandai.out","w",stdout);
printf("%.1lf\n",(double)ans/2);
}
int main()
{
read();
solve();
write();
return 0;
}