Mai intai trebuie sa te autentifici.
Cod sursa(job #1774433)
Utilizator | Data | 8 octombrie 2016 22:34:32 | |
---|---|---|---|
Problema | Trapez | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.7 kb |
#include<fstream>
#include<math.h>
#include<vector>
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");
typedef pair<long long, long long> POINT2D;
POINT2D points[1010];
vector<POINT2D> H[666013];
long long Abs(long long x)
{
return (x > 0) ? x : -x;
}
long long get_key(POINT2D p)
{
return (Abs(p.first) * 2 + Abs(p.second) * 3) % 666013;
}
void insert(POINT2D p)
{
H[get_key(p)].push_back(p);
}
bool compare(POINT2D &p1, POINT2D &p2)
{
return p1.first==p2.first && p1.second == p2.second;
}
bool findH(POINT2D p)
{
for (int i = 0; i < H[get_key(p)].size(); ++i)
if (compare(p, H[get_key(p)][i]))
return true;
return false;
}
int N;
long long cmmdc(long long a, long long b)
{
while (b)
{
long long r = a%b;
a = b;
b = r;
}
return a;
}
int main()
{
in >> N;
for (int i = 1;i <= N;++i)
in >> points[i].first >> points[i].second;
for (int i = 1;i <= N;++i)
{
for (int j = i+1;j <= N;++j)
{
if (points[i].first - points[j].first == 0)
{
if (!findH(make_pair(1LL << 50, 1LL << 50)))
insert(make_pair(1LL << 50, 1LL << 50));
}
else if (points[i].second - points[j].second == 0)
if (!findH(make_pair(0, 0)))
insert(make_pair(0, 0));
else
{
long long v_y = points[i].second - points[j].second, v_x = points[i].first - points[j].first;
long long cm = cmmdc(Abs(v_y), Abs(v_x));
if (v_y < 0 && v_x < 0)
v_x *= -1, v_y *= -1;
else if (v_x < 0 || v_y < 0)
{
if (v_x < 0)
v_y *= -1,v_x*=-1;
}
if (!findH(make_pair(v_y/cm, v_x/cm)))
insert(make_pair(v_y/cm, v_x/cm));
}
}
}
return 0;
}