Pagini recente » Cod sursa (job #127515) | Cod sursa (job #2454733) | Cod sursa (job #182684) | Profil Hecaton | Cod sursa (job #596590)
Cod sursa(job #596590)
# include <fstream>
# include <algorithm>
//# define eps 0.0001
# define r3 1.732
using namespace std;
std :: ifstream f ("triang.in");
std :: ofstream g ("triang.out");
struct punct
{
double x, y;
};
int n, i, j, sol;
punct v[1502];
double si=r3/2.0,co=0.5,eps=0.0001;
inline double mod (double a)
{
return a < 0 ? a * -1.0 : a;
}
inline bool egal (double a, double b)
{
return max (a, b) - min (a, b) < eps;
}
inline bool mic (double a, double b)
{
return a - b < eps;
}
inline punct p1 (punct a, punct b)
{
punct c;
c.x = a.x + (b.x - a.x) * co + (a.y - b.y)*si;
c.y = a.y + (b.x - a.x) * si - (a.y - b.y)*co;
return c;
}
inline punct p2 (punct a, punct b)
{
punct c;
c.x = a.x + (b.x - a.x) * co - (a.y - b.y)*si;
c.y = a.y - (b.x - a.x) * si - (a.y - b.y)*co;
return c;
}
inline int bs (int j, punct c)
{
int i, cnt = (1 << 11);
for (i = j + 1; cnt > 0; cnt >>= 1)
{
int aux = i + cnt;
if (aux <= n)
{
if (mic (v[aux].x, c.x) || (egal (v[aux].x, c.x) && mic (v[aux].y, c.y))) i = aux;
}
}
//if (i <= n)
return (egal (c.x, v[i].x) && egal (c.y, v[i].y) ? 1 : 0);
//else
//return 0;
}
inline bool cmp (punct a, punct b)
{
if (egal (a.x, b.x))
return mic (a.y, b.y);
return mic (a.x, b.x);
}
int main ()
{
f >> n;
for (i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
v[n + 1].x = v[n + 1].y = 100000;
sort (v + 1, v + n + 1, cmp);
for (i = 1; i < n-1; ++i)
for (j = i + 1; j < n; ++j)
{
if ( bs (j, p1 (v[i], v[j])) ) ++sol;
if ( bs (j, p2 (v[i], v[j])) ) ++sol;
}
g << sol << '\n';
g.close ();
return 0;
}