Cod sursa(job #3267997)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 13 ianuarie 2025 13:39:13
Problema Popandai Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("popandai.in");
ofstream fout("popandai.out");
int n,k,i,j;
double mn=1e9;
int pxa,pya,pxb,pyb,pxc,pyc,pxd,pyd;
struct numere
{
    int x,y;
}v[350];
vector<pair<double,int>>sol[305];
void read()
{
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
}
bool comp(pair<double,int> a,pair<double,int> b)
{
    return (a.first<b.first||(a.first==b.first&&a.second<b.second));
}
double arie(int pxa,int pya,int pxb,int pyb,int pxc,int pyc)
{
    return abs(pxb*pyc+pxa*pyb+pya*pxc-pxb*pya-pxc*pyb-pyc*pxa);
}
bool cond()
{
    int i,nr=0;
    for(i=1;i<=n;i++)
    {
        if((double)arie(pxa,pya,pxb,pyb,v[i].x,v[i].y)/2+(double)arie(pxb,pyb,pxc,pyc,v[i].x,v[i].y)/2+(double)arie(pxc,pyc,pxd,pyd,v[i].x,v[i].y)/2+(double)arie(pxa,pya,pxd,pyd,v[i].x,v[i].y)/2==(double)arie(pxa,pya,pxb,pyb,pxc,pyc)/2+(double)arie(pxa,pya,pxc,pyc,pxd,pyd)/2)
            nr++;
        if(nr>=k)return 1;
    }
    return 0;
}
void solve()
{
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i!=j)
            {
                double dist=(double)sqrt((v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y));
                sol[i].push_back({dist,j});
            }
        }
        sort(sol[i].begin(),sol[i].end(),comp);
        pxa=v[i].x;pya=v[i].y;
        pxb=v[sol[i][0].second].x;pyb=v[sol[i][0].second].y;
        pxc=v[sol[i][1].second].x;pyc=v[sol[i][1].second].y;
        pxd=v[sol[i][2].second].x;pyd=v[sol[i][2].second].y;
        if(cond())mn=min(mn,(double)arie(pxa,pya,pxb,pyb,pxc,pyc)/2+(double)arie(pxa,pya,pxc,pyc,pxd,pyd)/2);

    }
}
void af()
{
    fout<<mn;
}
int main()
{
    read();
    solve();
    af();
    return 0;
}