Pagini recente » Cod sursa (job #2874633) | Cod sursa (job #1186424) | Cod sursa (job #359005) | Cod sursa (job #809047) | Cod sursa (job #2256600)
#include<vector>
#include<fstream>
#include<algorithm>
#define f first
#define s second
#define INF 2000000000
using namespace std;
ifstream fin("popandai.in");
ofstream fout("popandai.out");
int n,k,i,j,h,a,b,c,sus[301][301],jos[301][301],up[301],down[301],punctaj,sum,val,sol;
int aux[4];
pair<int,int> v[301];
int arie(int x,int y,int x1,int y1,int x2,int y2)
{
int aux=(x1-x)*(y2-y)-(x2-x)*(y1-y);
if(aux<0)
return -aux;
return aux;
}
void calc(int i,int h, int j)
{
int a,b,c,sum;
a=v[i].s-v[j].s;
b=v[j].f-v[i].f;
c=v[i].f*(v[j].s-v[i].s)-v[i].s*(v[j].f-v[i].f);
sum=v[h].f*a+v[h].s*b+c;
if(sum>0)
punctaj=jos[i][h]+jos[h][j]-jos[i][j];
else
punctaj=sus[i][h]+sus[h][j]-sus[i][j];
}
int main()
{
fin>>n>>k;
for(i=1;i<=n;i++)
fin>>v[i].f>>v[i].s;
sort(v+1, v+n+1);
sol=INF;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
a=v[i].s-v[j].s;
b=v[j].f-v[i].f;
c=v[i].f*(v[j].s-v[i].s)-v[i].s*(v[j].f-v[i].f);
for(h=1;h<=n;h++)
{
if(v[h].f*a+v[h].s*b+c<0&&v[h].f>=v[i].f&&v[h].f<=v[j].f)
jos[i][j]++;
if(v[h].f*a+v[h].s*b+c>0&&v[h].f>=v[i].f&&v[h].f<=v[j].f)
sus[i][j]++;
}
}
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
for(h=0;h<=300;h++)
up[h]=INF,down[h]=INF;
a=v[i].s-v[j].s;
b=v[j].f-v[i].f;
c=v[i].f*(v[j].s-v[i].s)-v[i].s*(v[j].f-v[i].f);
for(h=1;h<=n;h++)
{
sum=v[h].f*a+v[h].s*b+c;
if(sum!=0)
{
aux[1]=i;aux[2]=j;aux[3]=h;
sort(aux+1, aux+4);
calc(aux[1],aux[2],aux[3]);
val=arie(v[i].f,v[i].s,v[j].f,v[j].s,v[h].f,v[h].s);
if(sum>0)
up[punctaj]=min(up[punctaj], val);
if(sum<0)
down[punctaj]=min(down[punctaj], val);
}
}
for(h=299;h>=0;h--)
up[h]=min(up[h],up[h+1]),down[h]=min(down[h],down[h+1]);
for(h=0;h<=k;h++)
if(up[h]!=INF&&down[k-h]!=INF)
sol=min(sol, up[h]+down[k-h]);
}
if(sol%2==0)
fout<<sol/2<<".0";
else
fout<<sol/2<<".5";
return 0;
}