Pagini recente » Cod sursa (job #1225905) | Borderou de evaluare (job #2078141) | Cod sursa (job #2650492) | Cod sursa (job #2195236) | Cod sursa (job #50626)
Cod sursa(job #50626)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define NMAX 330
#define x first
#define y second
#define INF 666666
#define eps 0.0000001
#define MAX(a,b) (((a)-(b)>eps) ? (a):(b))
using namespace std;
struct pp
{
int a, b, c;
} Pp[3];
bool operator<(const struct pp &x, const struct pp &y)
{
return ( (x.a<y.a) || (x.a==y.a && x.b<y.b) );
}
int Under[NMAX][NMAX], N, K;
vector<pair<int,int> > P;
double Amax=INF, Up[NMAX], Down[NMAX];
int main()
{
int i, j, k, x, y, ii, jj, kk;
double xjos, yjos, sup;
int x1,x2,x3,y1,y2,y3,det;
freopen("popandai.in", "r", stdin);
scanf("%d %d", &N, &K);
for (i = 1; i <= N; i++){
scanf("%d %d", &x, &y);
P.push_back(make_pair(x,y)); }
sort(P.begin(), P.end());
for (i = 0; i < N; i++)
for (j = i+1; j < N; j++)
{
x2 = P[i].x; y2 = P[i].y; x3 = P[j].x; y3 = P[j].y;
for (k = 0; k < N; k++)
if ((i!=k&&j!=k)&&(P[i].x <= P[k].x && P[k].x <= P[j].x))
{
x1 = P[k].x; y1 = P[k].y;
det = x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
Under[i][j] += (det<0);
}
Under[j][i] = Under[i][j];
}
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
{
memset(Up,0,sizeof(Up));
memset(Down,0,sizeof(Down));
for (k = 0; k < N; k++)
if (i != j && i != k && j != k)
{
Pp[0].a = P[i].x; Pp[0].b = P[i].y; Pp[0].c = i;
Pp[1].a = P[j].x; Pp[1].b = P[j].y; Pp[1].c = j;
Pp[2].a = P[k].x; Pp[2].b = P[k].y; Pp[2].c = k;
sort(&Pp[0], &Pp[3]);
x1 = Pp[1].a; y1 = Pp[1].b; x2 = Pp[0].a; y2 = Pp[0].b; x3 = Pp[2].a; y3 = Pp[2].b;
ii = Pp[0].c; jj = Pp[1].c; kk = Pp[2].c;
det = x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
if ( det<0 )
{
Down[ x=Under[ii][kk]-Under[ii][jj]-Under[jj][kk] ] = MAX(0.5*abs(det),Down[ Under[ii][kk]-Under[ii][jj]-Under[jj][kk] ]);
if (x < 0)
return 1;
}
if ( det>0 )
{
Up[ x=Under[ii][jj]+Under[jj][kk]-Under[ii][kk] ] = MAX(0.5*abs(det),Up[ Under[ii][jj]+Under[jj][kk]-Under[ii][kk] ]);
if (x < 0)
return 1;
}
}
for (k = 0; k <= K; k++)
if ((Down[k]>eps && Up[K-k]>eps)&&(Amax > (Down[k]+Up[K-k])))
Amax = Down[k]+Up[K-k];
}
freopen("popandai.out", "w", stdout);
printf("%02lf\n", Amax);
return 0;
}