Pagini recente » Cod sursa (job #497030) | Cod sursa (job #2507753) | Cod sursa (job #1832329) | Cod sursa (job #452132) | Cod sursa (job #918149)
Cod sursa(job #918149)
#include <fstream>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
#define int64 long long
const int64 oo=1LL << 60;
const int Nmax=310;
#define x first
#define y second
typedef pair<int,int> Pair;
ifstream F("popandai.in");
ofstream G("popandai.out");
Pair V[Nmax];
int N,K,Banda[Nmax][Nmax];
int64 D[Nmax],Aria;
#define Formula (P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y)
#define Formula2 (Banda[A][B]+Banda[B][C]-Banda[A][C])
#define Formula3 (Banda[A][C]-Banda[A][B]-Banda[B][C]-1)
inline int Mod (int x) { return (x<0?-x:x);}
inline int Sign (const Pair& P1, const Pair& P2, const Pair& P3) { return (Formula<0?0:1); }
inline int Area (const Pair& P1, const Pair& P2, const Pair& P3) { return Mod(Formula); }
inline void Ord(int &A,int &B,int &C) { if (A>B) swap(A,B); if (A>C) swap(A,C); if (B>C) swap(B,C); }
inline int Count(int A, int B, int C) { Ord(A,B,C); return (Sign(V[A],V[C],V[B])==1) ? Formula2 : Formula3; }
int main ()
{
F >> N >> K;
for (int i=1; i<=N; ++i)
F >> 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 (Sign(V[i],V[j],V[k])==0) ++Banda[i][j];
Aria=oo;
for (int i=1; i<=N; ++i)
for (int j=i+1; j<=N; ++j)
{
int c,s;
for (int k=0; k<=N+1; ++k) D[k]=oo;
for (int k=1; k<=N; ++k)
if ( k!=i && k!=j && Sign(V[i],V[j],V[k])==0 )
c=Count(i,j,k), D[c]=min(D[c],1LL*Area(V[i],V[j],V[k]));
for (int k=N; k>=0; k--)
D[k]=min(D[k],D[k+1]);
for (int k=1; k<=N; ++k)
if ( k!=i && k!=j && Sign(V[i],V[j],V[k])==1 )
{
c=Count(i,j,k);
s=K-c;
if (s<0) s=K;
if (D[s]==oo) continue;
Aria=min(Aria,Area(V[i],V[j],V[k])+D[s]);
}
}
G << fixed << setprecision(1) << (1.0*Aria)/2 << '\n';
}