Pagini recente » Cod sursa (job #908170) | Cod sursa (job #2368784) | Cod sursa (job #2139700) | Cod sursa (job #1888013) | Cod sursa (job #981156)
Cod sursa(job #981156)
#include <cstdio>
#include <utility>
#include <algorithm>
typedef std::pair<int,int> Point;
const int MAX_N(1001);
const int MAX_VALUE(1 << 30);
const double GUARD(0.0000001);
struct Line
{
double slope;
double a;
double b;
double c;
} v [MAX_N * MAX_N];
bool operator < (struct Line a, struct Line b)
{
return a.slope < b.slope;
}
int n, end, Result;
Point p [MAX_N];
inline void Read (void)
{
std::freopen("trapez.in","r",stdin);
std::scanf("%d",&n);
end = (n * (n - 1)) >> 1;
for (int index(1) ; index <= n ; ++index)
std::scanf("%d %d",&p[index].first,&p[index].second);
std::fclose(stdin);
}
inline void Print (void)
{
std::freopen("trapez.out","w",stdout);
std::printf("%d\n",Result);
std::fclose(stdout);
}
inline bool Intersect (struct Line x, struct Line y)
{
return x.a * y.b - x.b * y.a;
}
inline void Compute (void)
{
int i, j, index(1);
for (i = 1 ; i <= n ; ++i)
for (j = i + 1 ; j <= n ; ++j)
{
v[index].a = p[j].second - p[i].second;
v[index].b = p[i].first - p[j].first;
v[index].c = v[index].a * p[i].first + v[index].b * p[i].second;
if (p[i].first == p[j].first)
v[index].slope = MAX_VALUE;
else
v[index].slope = (p[j].second - p[i].second) / (p[j].first - p[i].first);
++index;
}
std::sort(v + 1,v + end + 1);
i = 1;
while (i <= end)
{
for (j = i + 1 ; j <= end && v[j].slope >= v[i].slope - GUARD && v[j].slope <= v[i].slope + GUARD ; ++j)
/* do nothing */;
if (v[i].slope == 0)
{
int k;
while (i < j)
{
for (k = i + 1 ; k < j ; ++k)
if (!Intersect(v[i],v[k]))
++Result;
++i;
}
}
else
{
Result += ((j - i) * (j - i - 1)) >> 1;
i = j;
}
}
}
int main (void)
{
Read();
Compute();
Print();
return 0;
}