Pagini recente » Cod sursa (job #610757) | Cod sursa (job #3248185) | Cod sursa (job #1345457) | Cod sursa (job #1359709)
#include<fstream>
#include<iomanip>
using namespace std;
ifstream in("popandai.in");
ofstream out("popandai.out");
struct punct{
long long x, y;
};
const int nmax = 306, inf = 1000000000;
int n, k, poz[nmax];
punct v[nmax];
int vmagic[nmax][nmax];
double rasp = inf;
inline long long modul(long long x)
{
if(x<0)
return -x;
else
return x;
}
inline int aria(punct a, punct b, punct c)
{
return modul(a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y);
}
inline int det(punct a,punct b,punct c)
{
return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}
bool esub(int i, int j, int h)
{
int rlim = max(v[i].x, v[j].x), llim = min(v[i].x, v[j].x);
int aux;
if(v[i].x<v[j].x)
aux = det(v[j], v[i], v[h]);
else
aux = det(v[i], v[j], v[h]);
if(h!=i && h!=j && v[h].x<=rlim && v[h].x>llim && aux<=0)
return 1;
else
return 0;
}
int main(){
int player_unu=0;
out<<setprecision(1)<<fixed;
in>>n>>k;
for(int i = 1; i<=n; i++)
{
in>>v[i].x>>v[i].y;
}
for(int i = 1; i<=n; i++)
{
for(int j = i + 1; j<=n; j++)
{
for(int h = 1; h<=n; h++)
{
vmagic[i][j] += esub(i, j, h);
}
vmagic[j][i] = vmagic[i][j];
}
}
for(int i = 1; i<=n; i++)
{
for(int j = i + 1; j<=n; j++)
{
for(int h = 0; h<n; h++)
poz[h] = inf;
for(int h = 1; h<=n; h++)
{
int aux1;
if(v[i].x<v[j].x)
aux1 = det(v[j], v[i], v[h]);
else
aux1 = det(v[i], v[j], v[h]);
if(h!=i && h!=j && aux1<=0)
{
int aux = modul(vmagic[i][j] - vmagic[h][j] - vmagic[h][i]) - esub(i, j, h);
poz[aux] = min(poz[aux], aria(v[i], v[j], v[h]));
}
}
for(int h = 1; h<=n; h++)
{
int aux1;
if(v[i].x<v[j].x)
aux1 = det(v[j], v[i], v[h]);
else
aux1 = det(v[i], v[j], v[h]);
if(h!=i && h!=j && aux1>0)
{
int aux = k - modul(vmagic[i][j] - vmagic[h][j] - vmagic[h][i]) + esub(j, h, i) + esub(h, i , j);
if(aux>=0)
{
if(poz[aux] + aria(v[i], v[j], v[h])<rasp)
rasp = poz[aux] + aria(v[i], v[j], v[h]);
}
}
}
}
}
out<<rasp / 2<<'\n';
return player_unu;
}