Cod sursa(job #3198393)

Utilizator TheEpicWipedCreaVlad Chirita Alexandru TheEpicWipedCrea Data 29 ianuarie 2024 10:53:30
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.34 kb
#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;
}