Pagini recente » Cod sursa (job #2452146) | Cod sursa (job #823765) | Cod sursa (job #1463967) | Cod sursa (job #2083080) | Cod sursa (job #596555)
Cod sursa(job #596555)
# include <fstream>
# include <algorithm>
# define eps 0.001
# 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[1501];
double si=r3/2.0,co=0.5;
inline double mod (double a)
{
return a < 0 ? -a : a;
}
inline bool egal (double a, double b)
{
return mod (a - b) < eps;
}
inline bool mic (double a, double b)
{
return a - b <= 0;
}
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 (punct c,int k)
{
int i, cnt = (1 << 11);
for (i = k; 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;
}
}
return (egal (c.x, v[i].x) && egal (c.y, v[i].y) ? i : 0);
}
inline bool cmp (punct a, punct b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int main ()
{
f >> n;
for (i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
sort (v + 1, v + n + 1, cmp);
for (i = 1; i < n-1; ++i)
for (j = i + 1; j < n; ++j)
{
if ( bs (p1 (v[i], v[j]),j+1) ) ++sol;
if ( bs (p2 (v[i], v[j]),j+1) ) ++sol;
}
g << sol << '\n';
g.close ();
return 0;
}