Pagini recente » Cod sursa (job #1025060) | Cod sursa (job #2778164) | Cod sursa (job #3153423) | Autentificare | Cod sursa (job #1081314)
#include <fstream>
#include <cmath>
#define nru 1501
using namespace std;
ofstream out("triang.out");
ifstream in("triang.in");
int n;
struct ind
{
double a,b;
};
ind v[nru];
void quicksort(int f,int n)
{
int i=f, j=n,p=f;
while(i<=j)
{
while(v[i].a<v[p].a)
i++;
while(v[j].a>v[p].a)
j--;
if(i<=j)
{
swap(v[i],v[j]);
if(v[i].a==v[j].a)
if(v[i].b>v[j].b)swap(v[i].b,v[j].b);
i++;
j--;
}
}
if(f<j)
quicksort(f,j);
if(i<n)
quicksort(i,n);
}
int com(ind x, ind y)
{
if(abs(x.a-y.a)<0.0001)
{
if(abs(x.b-y.b)<0.0001) return 0;
else
if(x.b>y.b) return 1;
else return -1;
}
if(x.a>y.a) return 1;
else return -1;
}
int caut(ind x)
{
int i=1,f=n,m,ok;
ind y;
while(i<=f)
{
m=i+(-i+f)/2;
y.a=v[m].a; y.b=v[m].b;
ok=com(x,y);
if(ok==0) return 1;
if(ok<0) i=m+1;
else f=m-1;
}
return 0;
}
int main()
{
int i,j;
ind x;
long long s=0;
in>>n;
for(int i=1;i<=n;++i)
in>>v[i].a>>v[i].b;
quicksort(1,n);
// for (i=1;i<=n;++i) out<<v[i].a<<' '<<v[i].b<<"\n";
for(i=1;i<n;++i)
for(j=i+1;j<=n;++j)
{
x.a=(v[j].a+v[i].a)*0.5-sqrt(3.0)*0.5*(v[j].b-v[i].b);
x.b=(v[j].b+v[i].b)*0.5+sqrt(3.0)*0.5*(v[j].a-v[i].a);
// out<<x.a<<' '<<x.b<<"\n";
s+=caut(x);
x.a=(v[j].a+v[i].a)*0.5+sqrt(3.0)*0.5*(v[j].b-v[i].b);
x.b=(v[j].b+v[i].b)*0.5-sqrt(3.0)*0.5*(v[j].a-v[i].a);
//out<<x.a<<' '<<x.b<<"\n";
s+=caut(x);
}
out<<s<<"\n";
return 0;
}