Pagini recente » Cod sursa (job #2029943) | Cod sursa (job #1799263) | Cod sursa (job #2250143) | Cod sursa (job #707044) | Cod sursa (job #3196585)
#include <bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
std::ifstream f("gradina.in");
std::ofstream g("gradina.out");
struct coord{
int y, x, p;
};
int n, dm;
std::vector<coord> v;
std::vector<int> o;
inline int mod(int a){
return a<0 ? a*-1 : a;
}
int sqTrig(coord a, coord b){
if(a.y>b.y)
swap(a.y,b.y);
if(a.x>b.x)
swap(a.x,b.x);
return (b.y-a.y)*(b.x-a.x);
}
int orientation(coord a, coord b, coord c){
int r=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
return r<0;
}
coord cmp;
bool orcmp(coord a, coord b){
return orientation(cmp, a, b);
}
std::vector<coord> infas(std::vector<coord> a){
std::vector<coord> s;
int mn=INT_MIN;
int mi=0;
for(int i=0;i<a.size();i++)
if(mn<a[i].x){
mn=a[i].x;
mi=i;
}
swap(a[mi],a[0]);
cmp=a[0];
std::sort(a.begin()+1,a.end(),orcmp);
s.push_back(a[0]);
s.push_back(a[1]);
for(int i=2;i<a.size();i++){
int h=s.size()-1;
while(h>=1&&orientation(s[h-1],s[h],a[i])==0){
h--;
s.pop_back();
}
s.push_back(a[i]);
}
return s;
}
inline int areaof(coord a, coord b, int fl){
return mod(a.y-b.y)*(a.x-b.x)+(min(a.y,b.y)-fl)*(a.x-b.x)*2;
}
int surf(std::vector<coord> a){
int r=0, fl=INT_MAX;
for(auto it: a)
fl=min(fl,it.y);
for(int i=0;i<a.size()-1;i++){
r+=areaof(a[i],a[i+1],fl);
}
r+=areaof(a.back(),a.front(),fl);
r*=10;
r/=2;
return r;
}
void print(std::vector<coord> p){
for(auto it: p){
g<<it.y<<' '<<it.x<<'\n';
}
}
std::vector<int> split(coord a, coord b){
std::vector<coord> k;
std::vector<coord> j;
std::vector<int> r;
for(auto it: v){
if(orientation(a,b,it))
k.push_back(it);
else
j.push_back(it);
}
r.resize(2,0);
r[0]=INT_MAX;
if(k.size()<=2 || j.size()<=2)
return r;
r.resize(n+4);
for(auto it: k){
r[it.p]=1;
}
for(auto it: j){
r[it.p]=2;
}
k=infas(k);
j=infas(j);
//print(k);
//g<<surf(k)<<'\n';
if(r[1]==2)
for(int i=1;i<=n;i++)
r[i]=3-r[i];
r[0]=(mod(surf(k)-surf(j)));
return r;
}
bool resComp(std::vector<int> a, std::vector<int> b){
for(int i=1;i<=n;i++){
if(b[i]==2 && a[i]==1)
return 1;
if(a[i]==2 && b[i]==1)
return 0;
}
return 0;
}
int main(){
f>>n;
o.resize(n+2);
o[0]=INT_MAX;
for(int i=1;i<=n;i++){
int y, x;
f>>y>>x;
v.push_back({y,x,i});
}
//g<<areaof({4,3},{4,5},1);
//return 0;
//for(auto it: v){
// g<<it.y<<' '<<it.x<<'\n';
//}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
std::vector<int> s=split(v[j-1],v[i-1]);
if(s[1]){
if(o[0]>s[0])
o=s;
//if(s[0]==o[0] && resComp(s,o))
// o=s;
}
}
}
}
g<<std::setprecision(1)<<std::fixed;
g<<double(o[0])/10<<'\n';
for(int i=1;i<=n;i++){
if(o[i]==1)
g<<'I';
else
g<<'V';
}
return 0;
}