Cod sursa(job #3366296)

Utilizator serbanbBrindescu Serban serbanb Data 30 septembrie 2026 15:12:01
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

struct point
{
    long long int x,y;
};

const int NMAX = 1e3;

int n;

point v[NMAX * NMAX + 5];
vector<pair<long long int, long long int>> lines;

void read()
{
    fin >> n;
    for(int i = 0; i < n; ++i){
        fin >> v[i].x >> v[i].y;
    }
}

long long int gcd(long long int a, long long int b)
{
    long long int r;
    while(b > 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void buildLines()
{
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            long long int dx = v[i].x - v[j].x, dy = v[i].y - v[j].y;
            if(dx == 0){
                dy = 1;
            }
            else if(dy == 0){
                dx = 1;
            }
            else{
                long long int d = gcd(abs(dx), abs(dy));
                dx /= d;
                dy /= d;
                if(dx < 0){
                    dx = -dx;
                    dy = -dy;
                }
            }
            lines.push_back(make_pair(dx, dy));
        }
    }
}

void solve()
{
    sort(lines.begin(), lines.end());
    long long int cnt = 1, ans = 0;
    for(int i = 1; i < lines.size(); ++i){
        if(lines[i].first == lines[i - 1].first && lines[i].second == lines[i - 1].second){
            ++cnt;
        }
        else{
            ans += (cnt - 1) * cnt / 2;
            cnt = 1;
        }
    }
    ans += (cnt - 1) * cnt / 2;
    fout << ans;
}

int main()
{
    read();
    buildLines();
    solve();
    return 0;
}