Cod sursa(job #1401988)

Utilizator ThomasFMI Suditu Thomas Thomas Data 26 martie 2015 11:33:27
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

#define NMax 1505

ifstream f("triang.in");
ofstream g("triang.out");

struct point{double x,y;};

point a[NMax];

inline double atg(point a,point b){
    return (double)(a.y-b.y)/(a.x-b.x);
}

inline double dist(point a,point b){
    return (double)sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int search(int l,int r,double x,double y){
    if(l>r) return 0;
    int mid=(l+r)/2;
    if(fabs(a[mid].x-x)<0.001 && fabs(a[mid].y-y)<0.001)
        return mid;
    if(a[mid].x<x)
        return search(mid+1,r,x,y);
    return search(l,mid-1,x,y);
}

struct comp{
    bool operator()(const point &a,const point &b){
        if(a.x==b.x) return a.y < b.y;
        return a.x < b.x;
    }
};

int main()
{
    int i,j,n,nr=0;
    f >> n;
    for(i=0;i<n;i++){
        f >> a[i].x >> a[i].y;
    }
    sort(a,a+n,comp());

    for(i=0;i<n-2;i++){
        for(j=i+1;j<n-1;j++){
            point mid;
            mid.x=(double)fabs(a[i].x-a[j].x)/2+a[i].x;
            mid.y=(double)fabs(a[i].y-a[j].y)/2+min(a[i].y,a[j].y);
            double alfa=atg(a[i],a[j]);
            double phi=-(1/alfa);
            double l=dist(a[i],a[j]);
            double h=l*sqrt(3)/2;
            double k=h*h/(phi*phi+1);
            if(search(j+1,n-1,mid.x+sqrt(k),phi*sqrt(k)+mid.y)!=0) nr++;
            if(search(j+1,n-1,mid.x-sqrt(k),mid.y-phi*sqrt(k))!=0) nr++;
        }
    }
    g << nr;

    f.close();
    g.close();
}