Cod sursa(job #3196585)

Utilizator RusuRRusu Rares RusuR Data 24 ianuarie 2024 12:12:48
Problema Gradina Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#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;
}