Pagini recente » Cod sursa (job #2373545) | Cod sursa (job #1242450) | Cod sursa (job #917513) | Cod sursa (job #296026) | Cod sursa (job #589218)
Cod sursa(job #589218)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,nrt,Log;
struct P{double x,y;}a[1503];
double dist(P x,P y)
{
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
bool equal(double x,double y)
{
if (fabs(x-y)>1e-3)return 0;
return 1;
}
bool compare(P t, P yt)
{
return t.x>yt.x;
}
int binary_search(P t,P t1,int q)
{
int step,i=q;
double dis;
dis=dist(t,t1);
for(step=Log,i=0;step>0;step>>=1)
if((i+step<n) && (dis<=dist(t1,a[i+step])) && (dis<=dist(t,a[i+step]))) i+=step;
return i;
}
int main()
{
int i,j,k;
ifstream in("triang.in");
in>>n;
for(i=0;i<n;i++)
in>>a[i].x>>a[i].y;
in.close();
for(Log=1;Log<n;Log<<=1);
sort(a,a+n,compare);
for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++)
{
int c=binary_search(a[i],a[j],j+1);
cout<<i<<' '<<j<<' '<<c<<'\n';
cout<<dist(a[i],a[j])<<' '<<dist(a[j],a[c])<<' '<<dist(a[c],a[i])<<'\n';
if(equal(dist(a[i],a[j]),dist(a[j],a[c]))&&equal(dist(a[j],a[c]),dist(a[c],a[i])))
nrt++;
}
system("pause");
ofstream("triang.out")<<nrt<<'\n';
return 0;
}