Pagini recente » Cod sursa (job #1855959) | Cod sursa (job #2457377) | Cod sursa (job #1559707) | Cod sursa (job #899135) | Cod sursa (job #843157)
Cod sursa(job #843157)
#include <fstream>
#include <cstring>
#include <iomanip>
#include <cassert>
#include <algorithm>
#define NM 310
#define x first
#define y second
using namespace std;
ifstream f("popandai.in");
ofstream g("popandai.out");
typedef pair<int, int> PI;
PI V[NM];
int N,K,i,j,k,c,s;
int Points[NM][NM];
const long long INF=999999999999999999;
long long D[NM],ANS=INF;
inline int Sign (const PI& P1, const PI& P2, const PI& P3)
{
int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
return (S<0?0:1);
}
inline int Mod (int x)
{
return (x<0?-x:x);
}
inline int Area (const PI& P1, const PI& P2, const PI& P3)
{
int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
return Mod(S);
}
inline int Count (int A, int B, int C)
{
if (A>B) swap(A,B);
if (A>C) swap(A,C);
if (B>C) swap(B,C);
if (Sign(V[A],V[C],V[B])==1)
return Points[A][B]+Points[B][C]-Points[A][C];
return Points[A][C]-Points[A][B]-Points[B][C]-1;
}
int main ()
{
f >> N >> K;
for (i=1; i<=N; i++)
f >> V[i].x >> V[i].y;
sort(V+1,V+N+1);
for (i=1; i<=N; i++)
for (j=i+1; j<=N; j++)
{
for (k=i+1; k<j; k++)
if (Sign(V[i],V[j],V[k])==0)
Points[i][j]++;
}
for (i=1; i<=N; i++)
for (j=i+1; j<=N; j++)
{
for (k=0; k<=N+1; k++)
D[k]=INF;
for (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 (k=N; k>=0; k--)
D[k]=min(D[k],D[k+1]);
for (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]==INF) continue;
ANS=min(ANS,Area(V[i],V[j],V[k])+D[s]);
}
}
g << fixed << setprecision(1) << (1.0*ANS)/2 << '\n';
f.close();
g.close();
return 0;
}