Cod sursa(job #2960003)

Utilizator cosmadrianAdrian Cosma cosmadrian Data 3 ianuarie 2023 13:49:43
Problema Trapez Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

ifstream fin("trapez.in");
ofstream fout("trapez.out");

struct Point {
    int x, y;
    Point() {}
    Point(int x, int y) : x(x), y(y) {}
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

struct Line {
    int a, b, c;
    Line() {}
    Line(int a, int b, int c) : a(a), b(b), c(c) {}
    bool operator<(const Line& l) const {
        return a < l.a || (a == l.a && b < l.b) || (a == l.a && b == l.b && c < l.c);
    }
};

int main() {
    int n;
    fin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        fin >> points[i].x >> points[i].y;
    }
    sort(points.begin(), points.end());
    map<Line, set<int>> lines;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int a = points[j].y - points[i].y;
            int b = points[i].x - points[j].x;
            int c = -a * points[i].x - b * points[i].y;
            int g = __gcd(__gcd(a, b), c);
            a /= g;
            b /= g;
            c /= g;
            if (a < 0 || (a == 0 && b < 0)) {
                a = -a;
                b = -b;
                c = -c;
            }
            lines[Line(a, b, c)].insert(i);
            lines[Line(a, b, c)].insert(j);
        }
    }
    int result = 0;
    for (const auto& line : lines) {
        result += line.second.size() * (line.second.size() - 1) / 2;
    }
    fout << result << "\n";
    return 0;
}