Pagini recente » Istoria paginii utilizator/dvd46328 | Rating Tom Horn (tomhorn) | Monitorul de evaluare | Cod sursa (job #271925) | Cod sursa (job #448046)
Cod sursa(job #448046)
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
typedef int int64;
struct trio
{
int64 x, y;
int64 z;
};
trio make_trio( int64 x, int64 y, int64 z )
{
trio aux;
aux.x = x, aux.y = y, aux.z = z;
return aux;
}
bool operator == ( trio a, trio b )
{
return a.x == b.x && a.y == b.y && a.z == b.z;
}
void read();
void write();
void comp();
inline int64 cmmdc( int64 a, int64 b )
{
if ( b == 0 )
return a;
return cmmdc( b, a % b );
}
inline int64 absol( int64 a )
{
return a < 0 ? a * -1 : a;
}
inline bool cmp( const trio& a, const trio& b )
{
if ( a.z != b.z )
return a.z < b.z;
if ( a.x != b.x )
return a.x < b.x;
return a.y <= b.y;
}
int64 n, cnt;
vector<trio> pct;
vector<trio> pnt;
int main()
{
read();
comp();
write();
return 0;
}
void read()
{
ifstream fin( "trapez.in" );
fin >> n;
pct.resize( n );
for ( int64 i = 0; i < n; ++i )
fin >> pct[i].x >> pct[i].y;
fin.close();
}
void write()
{
ofstream fout( "trapez.out" );
fout << cnt;
fout.close();
}
void comp()
{
for ( int64 i = 0; i < n - 1; ++i )
for ( int64 j = i + 1; j < n; ++j )
{
int64 ax1 = pct[i].y - pct[j].y,
ax2 = pct[i].x - pct[j].x;
int64 semn;
if ( ( ax1 >= 0 && ax2 >= 0 ) || ( ax1 < 0 && ax2 < 0 ) )
semn = 0;
else
semn = 1;
ax1 = absol(ax1), ax2 = absol(ax2);
if ( ax1 != 0 && ax2 != 0 )
{
int64 d = cmmdc( ax1, ax2 );
ax1 /= d, ax2 /= d;
}
else
{
if ( ax1 == 0 )
ax1 = ax2 = 0;
else
ax1 = ax2 = -1;
}
pnt.push_back( make_trio( ax1, ax2, semn ) );
}
sort( pnt.begin(), pnt.end(), cmp );
trio old;
old.x = old.y = -1;
int64 now = 1;
for ( int64 i = 0; i < (int64) pnt.size(); ++i )
if ( pnt[i] == old )
++now;
else
{
cnt += now * ( now - 1 ) / 2;
old = pnt[i];
now = 1;
}
}