Mai intai trebuie sa te autentifici.
Cod sursa(job #3143391)
Utilizator | Data | 29 iulie 2023 16:25:00 | |
---|---|---|---|
Problema | Trapez | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.13 kb |
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
if(!b)
return a;
return gcd(b, a % b);
}
bool comp(const vector<int>& a, const vector<int>& b)
{
if(a[0] != b[0])
return a[0] < b[0];
return a[1] < b[1];
}
int solve(vector<vector<int>> v)
{
int n = v.size(), ans = 0;
vector<vector<int>> arr;
int vert = 0;
for(int i = 0;i < n;++i)
for(int j = i + 1;j < n;++j)
{
int x = v[i][0] - v[j][0];
int y = v[i][1] - v[j][1];
if(!x)
++vert;
else
{
int gc = gcd(x, y);
arr.push_back({x / gc, y / gc});
}
}
ans += (vert * (vert - 1)) / 2;
sort(arr.begin(), arr.end(), comp);
int cnt = 1;
for(int i = 1;i < arr.size();++i)
{
if(arr[i] != arr[i - 1])
{
ans += (cnt * (cnt - 1)) / 2;
cnt = 1;
}
else
++cnt;
}
return ans + (cnt * (cnt - 1)) / 2;
}
int main() {
freopen("trapez.in", "r", stdin);
freopen("trapez.out", "w", stdout);
int n;
cin >> n;
vector<vector<int>> v;
for(int i = 0;i < n;++i)
{
vector<int> tmp(2);
cin >> tmp[0] >> tmp[1];
v.push_back(tmp);
}
cout << solve(v) << "\n";
}