Pagini recente » Cod sursa (job #184605) | Cod sursa (job #825903) | Cod sursa (job #535363) | Cod sursa (job #2462408) | Cod sursa (job #515505)
Cod sursa(job #515505)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 3000000000.0
#define NM 1005
int X[NM], Y[NM];
vector <double> pante;
int egale (double n1, double n2)
{
if (fabs(n1-n2) <= 0.0000001) return 1;
return 0;
}
int compara (double n1, double n2)
{
if (egale(n1, n2)) return 0;
if (n1 > n2) return 1;
return -1;
}
int main()
{
int N, ans = 0;
freopen ("trapez.in", "r", stdin);
freopen ("trapez.out", "w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; ++i) scanf ("%d %d", &X[i], &Y[i]);
for (int i = 1; i <= N; ++i)
for (int j = i + 1; j <= N; ++j)
{
double sus = Y[j] - Y[i];
double jos = X[j] - X[i];
double m;
if (egale (jos, 0)) m = inf;
else m = sus/jos;
//printf ("%d %d %lf\n", i, j, m);
pante.push_back(m);
}
sort (pante.begin(), pante.end());
/*
for (int i = 0; i < pante.size(); ++i) printf ("%lf ", pante[i]);
printf ("\n");
*/
for (int i = 1; i <= N; ++i)
for (int j = i + 1; j <= N; ++j)
{
double sus = Y[j] - Y[i];
double jos = X[j] - X[i];
double m;
if (egale (jos, 0)) m = inf;
else m = sus/jos;
int prim, ultim;
// prima valoare egala cu m
int st = 0, dr = pante.size() - 1;
while (st < dr)
{
int mij = (st + dr)/2;
if (compara(m, pante[mij]) <= 0) dr = mij;
else st = mij + 1;
}
prim = st;
// ultima valoare egala cu m
st = 0, dr = pante.size() - 1;
while (st < dr - 1)
{
int mij = (st + dr)/2;
if (compara(m, pante[mij]) >= 0) st = mij;
else dr = mij - 1;
}
if (egale (m, pante[dr])) st = dr;
ultim = st;
//printf ("%d %d %d %d\n", i, j, prim, ultim);
ans += (ultim - prim);
}
printf ("%d", ans/2);
return 0;
}