Cod sursa(job #2603621)

Utilizator LorenaMariaHantig Lorena LorenaMaria Data 20 aprilie 2020 14:38:50
Problema Gradina Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");
int n,s[251];
char t[251];
double mini=1000000000000;
struct pct
{ int x,y,id;
}a[251];
vector <pct> v[2];
bool cmp(pct a,pct b)
{ if(a.y==b.y)
     return a.x<b.x;
  return a.y<b.y;
}
bool stanga(pct a,pct b,pct c)
{ return (a.x-b.x)*(c.y-b.y)<(a.y-b.y)*(c.x-b.x);
}
void solve(int ok,pct a,pct b,pct c,int k)
{ if(v[ok].size()<k)
  { v[ok].push_back(c);
    return;
  }
  while(v[ok].size()>=k && !stanga(v[ok][v[ok].size()-2],v[ok][v[ok].size()-1],c))
    v[ok].pop_back();
  v[ok].push_back(c);
}
double aria(pct a,pct b,pct c)
{ return abs((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x))/2.0;
}
int main()
{ in>>n;
  for(int i=1;i<=n;i++)
    in>>a[i].x>>a[i].y,a[i].id=i;
  sort(a+1,a+n+1,cmp);
  for(int x=1;x<=n;x++)
  { for(int y=1;y<=n;y++)
    { if(x==y)
         continue;
      for(int i=1;i<=n;i++)
      { if(((a[x].x-a[y].x)*(a[i].y-a[y].y)>=(a[x].y-a[y].y)*(a[i].x-a[y].x) && i!=y) || i==x)
           solve(0,a[x],a[y],a[i],2),s[a[i].id]=0;
        else
           solve(1,a[x],a[y],a[i],2),s[a[i].id]=1;
      }
      int k0=v[0].size()+1,k1=v[1].size()+1;
      for(int i=n-1;i>=1;i--)
      { if(((a[x].x-a[y].x)*(a[i].y-a[y].y)>=(a[x].y-a[y].y)*(a[i].x-a[y].x) && i!=y) || i==x)
           solve(0,a[x],a[y],a[i],k0),s[a[i].id]=0;
        else
           solve(1,a[x],a[y],a[i],k1),s[a[i].id]=1;
      }
      if(v[0].size()<4 || v[1].size()<4)
      { v[0].clear();
        v[1].clear();
        continue;
      }
      v[0].pop_back();
      v[1].pop_back();
      k0=v[0].size();
      k1=v[1].size();
      double r0=0;
      for(int i=1;i<k0-1;i++)
        r0+=aria(v[0][i],v[0][i+1],v[0][0]);
      double r1=0;
      for(int i=1;i<k1-1;i++)
        r1+=aria(v[1][i],v[1][i+1],v[1][0]);
      if(mini>abs(r1-r0))
      { mini=abs(r1-r0);
        for(int i=1;i<=n;i++)
          if(s[i]==s[1])
             t[i]='I';
          else
             t[i]='V';
      }
      v[0].clear();
      v[1].clear();
    }
  }
  out<<setprecision(1)<<fixed<<mini<<'\n';
  for(int i=1;i<=n;i++)
    out<<t[i];
  in.close();
  out.close();
  return 0;
}