Cod sursa(job #3198011)

Utilizator Teodor94Teodor Plop Teodor94 Data 27 ianuarie 2024 23:29:31
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <bits/stdc++.h>
using namespace std;

#define int64 long long

#define MAX_N 250
#define EPS 0.001

struct Point { int x, y; };

int noPoints;
Point points[MAX_N];

Point points1[MAX_N], points2[MAX_N];
int noPoints1, noPoints2;
string pointsStr;
vector<Point> hull;

inline int64 orientation(const Point& a, const Point& b, const Point& c) {
    return ((int64)b.y - a.y) * (c.x - b.x) - ((int64)b.x - a.x) * (c.y - b.y);
}

inline bool cmpPoints1(const Point& a, const Point& b) {
    return orientation(points1[0], a, b) < 0;
}

inline bool cmpPoints2(const Point& a, const Point& b) {
    return orientation(points2[0], a, b) < 0;
}

void splitPoints(const Point& a, const Point& b) {
    int i;
    
    noPoints1 = noPoints2 = 0;
    pointsStr.clear();
    for (i = 0; i < noPoints; ++i) {
        if (orientation(a, b, points[i]) < 0)
            points1[noPoints1++] = points[i], pointsStr += 'I';
        else
            points2[noPoints2++] = points[i], pointsStr += 'V';
    }
}

void setStartPoint(Point* points, int noPoints) {
    int i;

    for (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 computeHull(Point* points, int noPoints) {
    int i;
    
    hull.clear();
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    
    for (i = 2; i < noPoints; ++i) {
        while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) >= 0)
            hull.pop_back();
        
        hull.push_back(points[i]);
    }
}

bool checkSplit() {
    if (noPoints1 < 3 || noPoints2 < 3)
        return false;
    
    setStartPoint(points1, noPoints1);
    sort(points1, points1 + noPoints1, cmpPoints1);
    computeHull(points1, noPoints1);
    if ((int)hull.size() != noPoints1) return false;
    
    setStartPoint(points2, noPoints2);
    sort(points2, points2 + noPoints2, cmpPoints2);
    computeHull(points2, noPoints2);
    if ((int)hull.size() != noPoints2) return false;
    
    return true;
}

double triangleArea(Point p1, Point p2, Point p3) {
    return (double)((int64)p1.x * (p2.y - p3.y) + (int64)p2.x * (p3.y - p1.y) + (int64)p3.x * (p1.y - p2.y)) / 2;
}

double computeArea(Point* points, int noPoints) {
    int i;
    double area;
    
    area = 0;
    for (i = 2; i < noPoints; ++i)
        area += triangleArea(points[0], points[i - 1], points[i]);
        
    return area;
}

int main() {
    FILE *fin, *fout;
    fin = fopen("gradina.in", "r");
    fout = fopen("gradina.out", "w");
    
    int i, j;
    double areaDiff, minAreaDiff;
    string minPointsStr;
    
    fscanf(fin, "%d", &noPoints);
    for (i = 0; i < noPoints; ++i)
        fscanf(fin, "%d%d", &points[i].x, &points[i].y);
    
    minAreaDiff = DBL_MAX, minPointsStr = "X";
    for (i = 0; i < noPoints; ++i)
        for (j = 0; j < noPoints; ++j)
            if (i != j) {
                splitPoints(points[i], points[j]);
                if (checkSplit()) {
                    areaDiff = abs(computeArea(points1, noPoints1) - computeArea(points2, noPoints2));
                    if (abs(areaDiff - minAreaDiff) < EPS && pointsStr < minPointsStr)
                        minPointsStr = pointsStr;
                    else if (areaDiff < minAreaDiff)
                        minAreaDiff = areaDiff, minPointsStr = pointsStr;
                }
            }
    
    fprintf(fout, "%.1lf\n", minAreaDiff);
    fprintf(fout, "%s\n", minPointsStr.c_str());
    
    fclose(fin);
    fclose(fout);
    return 0;
}