Pagini recente » Cod sursa (job #947043) | Cod sursa (job #2300009) | Cod sursa (job #144192) | Cod sursa (job #2457658) | Cod sursa (job #848219)
Cod sursa(job #848219)
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
# define pi M_PI
# define maxN 1505
typedef struct point {
double x, y;
};
int N;
point P[maxN];
void read()
{
ifstream f("triang.in");
f>> N;
int i;
for(i = 1; i <= N; ++i)
f>> P[i].x >> P[i].y;
f.close();
}
int equal(point a, point b)
{
if(fabs(a.x - b.x) < 0.001 && fabs(a.y - b.y) < 0.001)
return 1;
return 0;
}
bool compare(point a, point b)
{
if(fabs(a.x - b.x) < 0.001)
return a.y < b.y;
return a.x < b.x;
}
int exist(int l, int r, point p)
{
int m;
while(l < r)
{
m = (l + r) / 2;
if(equal(P[m], p))
return 1;
if(P[m].x < p.x || (fabs(P[m].x - p.x) < 0.001 && P[m].y < p.y))
l = m + 1;
else
r = m - 1;
}
if(equal(P[l], p))
return 1;
return 0;
}
void solve()
{
double cos60, cos300, sin60, sin300;
point p;
int i, j, result = 0;
cos300 = cos60 = cos(pi / 3);
sin60 = sin(pi / 3); sin300 = -sin60;
for (i = 1; i < N - 1; ++i)
for (j = i + 1; j < N; ++j)
{
p.x = P[i].x + (P[j].x - P[i].x) * cos60 - (P[j].y - P[i].y) * sin60;
p.y = P[i].y + (P[j].x - P[i].x) * sin60 + (P[j].y - P[i].y) * cos60;
if (p.x > P[j].x || (P[j].x == p.x && p.y > P[j].y))
if (exist(j + 1, N, p)) ++result;
p.x = P[i].x + (P[j].x - P[i].x) * cos300 - (P[j].y - P[i].y) * sin300;
p.y = P[i].y + (P[j].x - P[i].x) * sin300 + (P[j].y - P[i].y) * cos300;
if (p.x > P[j].x || (P[j].x == p.x && p.y > P[j].y))
if (exist(j + 1, N, p)) ++result;
}
ofstream g("triang.out");
g<< result;
g.close();
}
int main()
{
read();
sort(P + 1, P + N + 1, compare);
solve();
return 0;
}