Pagini recente » Cod sursa (job #3262112) | Cod sursa (job #3132881) | Cod sursa (job #3177516) | Cod sursa (job #2850107) | Cod sursa (job #3198393)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("gradina.in");
ofstream out("gradina.out");
#define ll long long
#define MAX_N 250
#define EPS 0.001
struct point{
int x,y;
}points[MAX_N],points1[MAX_N],points2[MAX_N];
int nopoints;
int nopoints1,nopoints2;
string pointsStr;
vector<point> inf;
ll orientation(const point& a,const point& b,const point& c){
return ((ll)b.y-a.y)*(c.x-b.x)-((ll)b.x-a.x)*(c.y-b.y);
}
bool cmpP1(const point& a,const point& b){
return orientation(points1[0],a,b)<0;
}
bool cmpP2(const point& a,const point& b){
return orientation(points2[0],a,b)<0;
}
void halfen(const point& a,const point& b){
nopoints1=0;
nopoints2=0;
pointsStr.clear();
for(int i=0;i<nopoints;i++){
if(orientation(a,b,points[i])<0){
points1[nopoints1]=points[i];
nopoints1++;
pointsStr+='I';
}
else{
points2[nopoints2]=points[i];
nopoints2++;
pointsStr+='V';
}
}
}
void start(point* points,int nopoints) {
for(int i=1;i<nopoints;i++){
if(points[i].y<points[0].y || (points[i].y==points[0].y && points[i].x<points[0].x)){
swap(points[0],points[i]);
}
}
}
void infasuratation(point* points,int nopoints) {
inf.clear();
inf.push_back(points[0]);
inf.push_back(points[1]);
for(int i=2;i<nopoints;i++){
while(inf.size()>=2 && orientation(inf[inf.size()-2],inf.back(),points[i])>=0){
inf.pop_back();
}
inf.push_back(points[i]);
}
}
bool checkHalf(){
if(nopoints1<3 || nopoints2<3){
return false;
}
start(points1,nopoints1);
sort(points1,points1+nopoints1,cmpP1);
infasuratation(points1,nopoints1);
if((int)inf.size()!=nopoints1){
return false;
}
start(points2,nopoints2);
sort(points2,points2+nopoints2,cmpP2);
infasuratation(points2,nopoints2);
if((int)inf.size()!=nopoints2){
return false;
}
return true;
}
double triangleArea(point p1,point p2,point p3){
return (double)((ll)p1.x*(p2.y-p3.y)+(ll)p2.x*(p3.y-p1.y)+(ll)p3.x*(p1.y-p2.y))/2;
}
double allarea(point* points,int nopoints){
double area=0;
for(int i=2;i<nopoints;i++){
area+=triangleArea(points[0],points[i-1],points[i]);
}
return area;
}
int main(){
in>>nopoints;
for(int i=0;i<nopoints;i++){
in>>points[i].x>>points[i].y;
}
double minAreaDiff=9999999999999;
string minpointsStr="X";
for(int i=0;i<nopoints;i++){
for(int j=0;j<nopoints;j++){
if(i!=j){
halfen(points[i],points[j]);
if(checkHalf()){
double areaDiff=abs( allarea(points1,nopoints1) - allarea(points2,nopoints2) );
if(abs(areaDiff-minAreaDiff)<EPS && pointsStr<minpointsStr){
minpointsStr=pointsStr;
}
else if(areaDiff<minAreaDiff){
minAreaDiff=areaDiff;
minpointsStr=pointsStr;
}
}
}
}
}
out<<fixed<<setprecision(1)<<minAreaDiff<<'\n';
out<<minpointsStr;
}