Cod sursa(job #2956232)

Utilizator Teodor94Teodor Plop Teodor94 Data 18 decembrie 2022 19:12:51
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <bits/stdc++.h>
using namespace std;

#define int64 long long

#define MAX_N 250

struct Point { int x, y; };

int noPoints;
Point points[MAX_N];

vector<Point> points1, points2;
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;
    
    points1.clear(), points2.clear();
    for (i = 0; i < noPoints; ++i)
        if (orientation(a, b, points[i]) < 0)
            points1.push_back(points[i]);
        else
            points2.push_back(points[i]);
}

void setStartPoint(vector<Point>& points) {
    unsigned int i;

    for (i = 1; i < points.size(); ++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(vector<Point>& points) {
    unsigned int i;
    
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    
    for (i = 2; i < points.size(); ++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 (points1.size() < 3 || points2.size() < 3)
        return false;
    
    setStartPoint(points1);
    sort(points1.begin(), points1.end(), cmpPoints1);
    computeHull(points1);
    if (hull.size() != points1.size()) return false;
    
    setStartPoint(points2);
    sort(points2.begin(), points2.end(), cmpPoints2);
    computeHull(points2);
    if (hull.size() != points2.size()) return false;
    
    return true;
}

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

double computeArea(const vector<Point>& points) {
    unsigned int i;
    double area;
    
    area = 0;
    for (i = 2; i < points.size(); ++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, k;
    double areaDiff, minAreaDiff;
    
    fscanf(fin, "%d", &noPoints);
    for (i = 0; i < noPoints; ++i)
        fscanf(fin, "%d%d", &points[i].x, &points[i].y);
    
    minAreaDiff = DBL_MAX;
    for (i = 0; i < noPoints; ++i)
        for (j = i + 1; j < noPoints; ++j) {
            printf("%d %d\n", i, j);
            splitPoints(points[i], points[j]);
            printf("%d %d\n", i, j);
            if (checkSplit()) {
                areaDiff = abs(computeArea(points1) - computeArea(points2));
                if (areaDiff < minAreaDiff)
                    minAreaDiff = areaDiff;
            }
            printf("%d %d\n", i, j);
        }
    
    fprintf(stdout, "%lf\n", minAreaDiff);
    
    fclose(fin);
    fclose(fout);
    return 0;
}