Pagini recente » Cod sursa (job #1190513) | Cod sursa (job #2705041) | Cod sursa (job #1370094) | Cod sursa (job #315002) | Cod sursa (job #1070694)
#include <fstream>
#include <algorithm>
#include <cmath>
#define Nmax 1505
#define eps 0.0001
#define sin60 sqrt(3.0) * 0.5
using namespace std;
int N;
struct coord
{
double x,y;
};
coord v[Nmax];
inline void Read()
{
ifstream fin("triang.in");
fin>>N;
for(int i=1;i<=N;++i)
fin>>v[i].x>>v[i].y;
fin.close();
}
inline bool cmp(const coord A, const coord B)
{
return (A.x<B.x || (A.x==B.x && A.y<B.y));
}
inline int Compara(coord A, coord B)
{
if(fabs(A.x-B.x)<eps)
{
if(fabs(A.y-B.y)<eps)
return 0;
else
if(A.y>B.y)
return 1;
else
return -1;
}
if(A.x>B.x)
return 1;
else
return -1;
}
inline int BSearch(coord A)
{
int st=1,dr=N,mij,ok;
coord B;
while(st<=dr)
{
mij=((st+dr)/2);
B.x=v[mij].x; B.y=v[mij].y;
ok=Compara(B,A);
if(!ok)
return 1;
if(ok<0)
st=mij+1;
else
dr=mij-1;
}
return 0;
}
int main()
{
int i,j;
coord A,B,C;
long long sol=0;
Read();
sort(v+1,v+N+1,cmp);
for(i=1;i<N;++i)
for(j=i+1;j<=N;++j)
{
A.x=v[i].x; A.y=v[i].y;
B.x=v[j].x; B.y=v[j].y;
C.x=(B.x+A.x)*0.5 - sin60*(B.y-A.y);
C.y=(B.y+A.y)*0.5 + sin60*(B.x-A.x);
sol+=BSearch(C);
C.x=(B.x+A.x)*0.5 + sin60*(B.y-A.y);
C.y=(B.y+A.y)*0.5 - sin60*(B.x-A.x);
sol+=BSearch(C);
}
sol/=3LL;
ofstream fout("triang.out");
fout<<sol<<"\n";
fout.close();
return 0;
}