Pagini recente » Cod sursa (job #152287) | Cod sursa (job #1974766) | Cod sursa (job #1591343) | Cod sursa (job #870846) | Cod sursa (job #822618)
Cod sursa(job #822618)
#include<fstream>
#include<algorithm>
#include<math.h>
using namespace std;
#define MAXN 1502
#define EPS 0.001
#define PI 3.1415926535
typedef struct { double x, y; } point;
int n, i, j, res, t;
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( fabs(A.x - v[mid].x) < EPS && fabs(A.y - v[mid].y) < EPS)
return mid;
else if( v[mid].x - A.x > EPS || ( (fabs(A.x - v[mid].x) < EPS) && v[mid].y - A.y > EPS) )
end = mid - 1;
else st = mid + 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(PI/3) - (Y2 - Y1) * sin(PI/3);
P.y = Y1 + (X2 - X1) * sin(PI/3) + (Y2 - Y1) * cos(PI/3);
t = bs(P);
if(t > j)
++res;
P.x = X1 + (X2 - X1) * cos(-PI/3) - (Y2 - Y1) * sin(-PI/3);
P.y = Y1 + (X2 - X1) * sin(-PI/3) + (Y2 - Y1) * cos(-PI/3);
t = bs(P);
if(t > j)
++res;
}
ofstream g("triang.out");
g << res << endl;
g.close();
return 0;
}