Pagini recente » Cod sursa (job #2592522) | Cod sursa (job #29490) | Cod sursa (job #3229495) | Cod sursa (job #2205295) | Cod sursa (job #615773)
Cod sursa(job #615773)
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
const char InFile[]="triang.in";
const char OutFile[]="triang.out";
const int MaxN=2048;
const double EPS=1.0e-3;
const double eps = 0.001;
const double sin60 = (1.7320508) * 0.5, cos60 = 0.5;
ifstream fin(InFile);
ofstream fout(OutFile);
struct s_point
{
double x,y;
};
int N,sol;
s_point p[MaxN];
inline bool d_equal(double a, double b)
{
return fabs(a-b)<EPS;
}
struct cmp
{
inline bool operator() (const s_point &a, const s_point &b)
{
if(!d_equal(a.x,b.x))
{
return a.x<b.x;
}
return a.y<b.y;
}
};
inline bool d_lower(double a, double b)
{
return a-b<EPS;
}
inline int bs(s_point &a, int st)
{
for(int step=1<<11;step;step>>=1)
{
int index=st+step;
if(index<=N)
{
if(d_lower(p[index].x,a.x) || (d_equal(p[index].x,a.x) && d_lower(p[index].y,a.y)))
{
st=index;
}
}
}
if(d_equal(a.x,p[st].x) && d_equal(a.y,p[st].y))
{
return 1;
}
return 0;
}
double dist(s_point a, s_point b)
{
double dx=a.x-b.x;
double dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
int main()
{
double sqrt2over3=sqrt(3.0)*0.5;
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>p[i].x>>p[i].y;
}
fin.close();
sort(p+1,p+1+N,cmp());
for(register int i=1;i<N-1;++i)
{
for(register int j=i+1;j<N;++j)
{
s_point C1;
C1.x=p[i].x+(p[j].x-p[i].x)*cos60+(p[j].y-p[i].y)*sin60;
C1.y=p[i].y-(p[j].x-p[i].x)*sin60+(p[j].y-p[i].y)*cos60;
s_point C2;
C2.x=p[i].x+(p[j].x-p[i].x)*cos60-(p[j].y-p[i].y)*sin60;
C2.y=p[i].y+(p[j].x-p[i].x)*sin60+(p[j].y-p[i].y)*cos60;
sol+=bs(C1,j+1);
sol+=bs(C2,j+1);
}
}
fout<<sol;
fout.close();
return 0;
}