Cod sursa(job #2530850)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 25 ianuarie 2020 13:04:27
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb

#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <algorithm>
#include <fstream>
#include <iomanip>
#define nmax 255
using namespace std;
struct point{int x;int y;int pos;};
int n,semn;
double sol,soltrue=1<<30;
char ss[nmax],q[nmax];
point v[nmax],aux;
point a[nmax],b[nmax];
point a1[nmax],b1[nmax];
deque <point> d;

int det(const point &a,const point &b,const point &c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmpsort(const point &a,const point &b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
double poligon(point a[],int m)
{
    int i,j=1,p;
    d.clear();
    d.push_back(a[1]);
    for (i=2;i<m;i++) {
        if (det(a[1],a[m],a[i])>=0)
            d.push_back(a[i]);
        else
            d.push_front(a[i]);
    }
    d.push_back(a[m]);

    int semn=det(d[d.size()-2],d[d.size()-1],d.front())>0;

    for (i=0;i<=d.size()-3;i++) {
        p=(det(d[i],d[i+1],d[i+2])>0);
        if ((p>0)!=semn)
            return 0;
    }
    double arie=0;
    for (i=0;i<=d.size()-2;i++)
        arie+=det(a[0],d[i],d[i+1]);
    arie+=det(a[0],d[d.size()-1],d.front());

    return abs(arie)/2.0;
}
int main()
{
    int i,j=1,t;
  ifstream f("gradina.in");
  ofstream g("gradina.out");
  f>>n;
    for (i=1;i<=n;i++) {
      f>>v[i].x>>v[i].y;
        v[i].pos=i;
    }
    int m,m1,k,k1;
    sort(v+1,v+n+1,cmpsort);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) {
            if (i==j)
                continue;
            m=k=0;
            for (t=1;t<=n;t++) {
                if (t==i) {
                    a[++m]=v[t];
                    continue;
                }
                if (t==j) {
                    b[++k]=v[t];
                    continue;
                }
                if (det(v[i],v[j],v[t])>0)
                   a[++m]=v[t];
                else
                    b[++k]=v[t];
            }
            if (m<3||k<3)
                continue;

            double s1=poligon(a,m);
            double s2=poligon(b,k);

            if (s1==0||s2==0)
                continue;

            sol=abs(s1-s2);

            if (sol<=soltrue) {
                for (t=1;t<=m;t++)
                    q[a[t].pos-1]='I';
                for (t=1;t<=k;t++)
                    q[b[t].pos-1]='V';
                if (q[0]=='V')
                    for (t=0;t<n;t++)
                        q[t]='I'+'V'-q[t];
                if (sol<soltrue||(sol==soltrue&&strcmp(q,ss)==0)) {
                    soltrue=sol;
                    strcpy(ss,q);
                }
            }
        }
g<<fixed<<setprecision(1)<<soltrue<<'\n'<<ss;

    return 0;
}