Pagini recente » Cod sursa (job #1823220) | Cod sursa (job #986409) | Cod sursa (job #305201) | Cod sursa (job #3036572) | Cod sursa (job #1814492)
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;
ifstream f("trapez.in");
ofstream g("trapez.out");
struct Punct {
int x, y;
};
struct Dreapta {
Punct A, B;
double panta;
};
double AflaPanta(Dreapta D)
{
if (D.B.x - D.A.x == 0)
return 2 << 30;
return (double)(D.B.y - D.A.y) / (double)(D.B.x - D.A.x);
}
void QuickSort(int st, int dr, vector<Dreapta> &v)
{
if (st < dr)
{
int i = st, j = dr;
Dreapta x = v[st];
while (i < j)
{
while (i < j && v[j].panta >= x.panta)
j--;
v[i] = v[j];
while (i < j && v[i].panta <= x.panta)
i++;
v[j] = v[i];
}
v[i] = x;
QuickSort(st, i - 1, v);
QuickSort(i + 1, dr, v);
}
}
int main()
{
int n, k = 0;
f >> n;
vector<Dreapta> v;
vector<Punct> p;
v.resize(n * (n - 1) / 2 + 1);
p.resize(n);
for (int i = 0; i < n; ++i)
f >> p[i].x >> p[i].y;
f.close();
for (int i = 0; i < n - 1; ++i)
for (int j = i + 1; j < n; ++j)
{
v[k].A = p[i];
v[k].B = p[j];
v[k].panta = AflaPanta(v[k]);
++k;
}
int nr = 1;
long long int sol = 0;
QuickSort(0, k - 1, v);
for (int i = 1; i < k; ++i)
{
if (v[i].panta == v[i - 1].panta)
++nr;
else
{
sol += (nr * (nr - 1)) / 2;
nr = 1;
}
}
g << sol;
g.close();
return 0;
}