Cod sursa(job #3223136)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 12 aprilie 2024 14:57:11
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <set>
#include <cassert>
#include <stack>
#include <algorithm>
#define ll long long

using namespace std;

ifstream cin("trapez.in");
ofstream cout("trapez.out");

const int NMAX = 1000;

struct Point
{
    int x, y;
    void Read()
    {
        cin >> x >> y;
    }
};

int n, indS;
ll answer, l;
Point points[NMAX + 1];
pair<ll, ll> slopes[NMAX * NMAX + 1];

int GCD(int a, int b)
{
    while(b)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

pair<int, int> GetSlope(Point p1, Point p2)
{
    int delta_y = p1.y - p2.y;
    int delta_x = p1.x - p2.x;

    if(delta_x == 0)
        return {0, 0}; /// Dreapta verticala

    if(delta_y == 0)
        return {0, 1}; /// Dreapta orizontala

    int gcd = GCD(delta_y, delta_x);
    delta_y /= gcd;
    delta_x /= gcd;
    return {delta_y, delta_x};
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        points[i].Read();

    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            slopes[++indS] = GetSlope(points[i], points[j]);

    sort(slopes + 1, slopes + indS + 1);

    l = 1;
    for(int i = 2; i <= indS; i++)
        if(slopes[i] == slopes[i - 1])
            l++;
        else
        {
            answer += l * (l - 1) / 2;
            l = 1;
        }
    answer += l * (l - 1) / 2;

    cout << answer;

    return 0;
}