Cod sursa(job #2123372)

Utilizator AndreiTudorSpiruAndrei Spiru AndreiTudorSpiru Data 6 februarie 2018 10:12:27
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct puncte
{
    double x,y;
}v[1501];
bool compare(puncte a,puncte b)
{
    return (a.x<b.x||(a.x==b.x&&a.y<b.y));
}
int binara(int p,int u,double c,double d)
{   int m;
    m=(p+u)/2;
    if(p>u)return 0;
    if(fabs(c-v[m].x)<0.001&&fabs(d-v[m].y)<0.001)return m;
    if(v[m].x<c)return binara(m+1,u,c,d);
    return binara(p,m-1,c,d);
}
int i,n,j;
double r;
long long k;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
   sort(v+1,v+n+1,compare);
   r=sqrt(3);
   for(i=1;i<n-1;i++)
    for(j=i+1;j<n;j++)
   {
       if(binara(j+1,n,(v[i].x+v[j].x)/2+r*(v[i].y-v[j].y)/2,(v[i].y+v[j].y)/2+r*(v[j].x-v[i].x)/2))
             k++;
      if(binara(j+1,n,(v[i].x+v[j].x)/2+r*(v[j].y-v[i].y)/2,(v[i].y+v[j].y)/2+r*(v[i].x-v[j].x)/2))
             k++;
   }
   g<<k;
    return 0;


}