Pagini recente » Cod sursa (job #3277210) | Cod sursa (job #826221) | Cod sursa (job #151974) | Cod sursa (job #2883972) | Cod sursa (job #1337902)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 305
using namespace std;
const long double INF=2000000000;
struct el
{
int nr;
long double aria;
} v1[Nmax],v2[Nmax];
struct Point
{
int x,y;
bool operator <(const Point A) const
{
return x<A.x;
}
} a[Nmax];
int pc[Nmax][Nmax],n,len1,len2;
long double minim[Nmax];
inline long long Semn(Point A, Point B, Point C)
{
return (1LL*(B.y-A.y)*C.x + 1LL*(A.x-B.x)*C.y + 1LL*B.x*A.y - 1LL*A.x*B.y);
}
inline long double Arie(Point A, Point B, Point C)
{
return 0.5*(double)abs(1LL*A.x*B.y + 1LL*B.x*C.y + 1LL*C.x*A.y - 1LL*C.x*B.y - 1LL*A.x*C.y - 1LL*B.x*A.y);
}
int main()
{
int i,j,k,nr;
long double sol=INF;
el w;
ifstream fin ("popandai.in");
ofstream fout ("popandai.out");
fin>>n>>nr;
for(i=1;i<=n;++i) fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
for(k=1;k<=n;++k)
if(a[k].x>a[i].x && a[k].x<a[j].x && a[k].y>0 && Semn(a[i],a[j],a[k])>0)
{
++pc[i][j];
++pc[j][i];
}
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
{
for(k=1,len1=len2=0;k<=n;++k)
if(Semn(a[i],a[j],a[k])>0)
{
//fout<<"jos "<<a[k].x<<" "<<a[k].y<<"\n";
w.aria=Arie(a[i],a[j],a[k]);
w.nr=pc[i][j]-pc[i][k]-pc[k][j];
v1[++len1]=w;
}
else
if(Semn(a[i],a[j],a[k])<0)
{
//fout<<"sus "<<a[k].x<<" "<<a[k].y<<"\n";
w.aria=Arie(a[i],a[j],a[k]);
w.nr=pc[i][k]+pc[k][j]-pc[i][j];
v2[++len2]=w;
}
for(k=0;k<=n;++k) minim[k]=INF;
for(k=1;k<=len2;++k) minim[v2[k].nr]=min(minim[v2[k].nr],v2[k].aria);
for(k=n-1;k>=0;--k) minim[k]=min(minim[k+1],minim[k]);
for(k=1;k<=len1;++k)
sol=min(sol,minim[max(nr-v1[k].nr,0)]+v1[k].aria);
}
fout<<setprecision(2)<<fixed<<sol<<"\n";
return 0;
}