Cod sursa(job #1963984)

Utilizator silkMarin Dragos silk Data 12 aprilie 2017 22:55:48
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <algorithm>
#define NMax 1500
#define x first
#define y second
using namespace std;

typedef pair<double, double> Point;
const double EPS = 0.0001;
Point v[NMax+1];
int N;

bool cmp(const Point A, const Point B)
{
    if(fabs(A.x-B.x) < EPS) return A.y < B.y;
    return A.x < B.x;
}

inline int CautBin(Point A)
{
    int st,dr,mid;

    for(st = 1, dr = N; st <= dr; )
    {
        mid = (st+dr)/2;
        if(fabs(A.x-v[mid].x) < EPS){
            if(fabs(A.y-v[mid].y) < EPS) return 1;
            else if(A.y < v[mid].y) dr = mid-1;
            else st = mid+1;
        } else {
            if(A.x < v[mid].x) dr = mid-1;
            else st = mid+1;
        }
    }

    return 0;
}

int main(){
    FILE* fin = fopen("triang.in","r");
    FILE* fout = fopen("triang.out","w");

    int i,j,res=0;
    double a,b;
    Point V;

    fscanf(fin,"%d",&N);
    for(i = 1; i <= N; ++i) fscanf(fin,"%lf %lf",&v[i].x,&v[i].y);

    a = 0.5;
    b = sqrt(3.0)/2;
    sort(v+1,v+N+1,cmp);
    for(i = 1; i < N; ++i)
        for(j = i+1; j <= N; ++j)
        {
            V.x = a * (v[i].x + v[j].x) + b * (v[i].y - v[j].y);
            V.y = a * (v[i].y + v[j].y) + b * (v[j].x - v[i].x);
            res = res + CautBin(V);

            V.x = a * (v[i].x + v[j].x) + b * (v[j].y - v[i].y);
            V.y = a * (v[i].y + v[j].y) + b * (v[i].x - v[j].x);
            res = res + CautBin(V);
        }

    fprintf(fout,"%d\n",res/3);


return 0;
}