Pagini recente » Cod sursa (job #1631832) | Cod sursa (job #3144192) | Cod sursa (job #1670481) | Cod sursa (job #476104) | Cod sursa (job #822378)
Cod sursa(job #822378)
#include<fstream>
#include<algorithm>
#include<math.h>
using namespace std;
#define MAXN 1502
#define EPS 0.001
#define sin_60 0.866
#define cos_60 0.5
typedef struct { double x, y; } point;
int n, i, j, res;
double X1, Y1, X2, Y2;
point P;
point v[ MAXN ];
inline int cmp(point A, point B)
{
if(A.x > B.x)
return 0;
if( fabs(A.x - B.x) < EPS && A.y > B.y)
return 0;
return 1;
}
inline int bs(point A)
{
int st = 1, end = n, mid;
while(st <= end)
{
mid = (st + end) / 2;
if(v[mid].x - A.x > EPS)
end = mid - 1;
else if(v[mid].x - A.x < -EPS)
st = mid + 1;
else
{
if(v[mid].y - A.y > EPS)
end = mid - 1;
else if(v[mid].y - A.y < -EPS)
st = mid + 1;
else return 1;
}
}
return 0;
}
int main()
{
ifstream f("triang.in");
f >> n;
for(i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
f.close();
sort(v+1, v+n+1, cmp);
for(i = 1; i <= n; ++i)
for(j = i + 1; j <= n; ++j)
{
X1 = v[i].x, Y1 = v[i].y;
X2 = v[j].x, Y2 = v[j].y;
P.x = X1 + (X2 - X1) * cos_60 - (Y2 - Y1) * sin_60;
P.y = Y1 + (X2 - X1) * sin_60 - (Y2 - Y1) * cos_60;
res += bs(P);
P.x = X1 + (X2 - X1) * (-cos_60) - (Y2 - Y1) * (-sin_60);
P.y = Y1 + (X2 - X1) * (-sin_60) - (Y2 - Y1) * (-cos_60);
res += bs(P);
}
ofstream g("triang.out");
g << res << endl;
g.close();
return 0;
}