Cod sursa(job #1033137)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 16 noiembrie 2013 15:04:27
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include<cstdlib>
using namespace std;
	
#define MAXN 1501
#define radical3 1.7320508075
#define MAXDIFF	2000000000
#define PI  3.141592653
double eps = 1e-3;

struct point 
{
	double x, y;
};
point p[MAXN];
int n;
point obt(point A, point B)
{
	point I;
	I.x = A.x + (cos(PI / 3.0)) * (B.x - A.x) - (sin(PI / 3.0)) * (B.y - A.y);
	I.y = A.y + (sin(PI / 3.0)) * (B.x - A.x) + (cos(PI / 3.0)) * (B.y - A.y);
	return I;
}
int cmp(double a, double b) {
    if(a + eps < b) return -1;
    if(b + eps < a) return 1;
    return 0;
}
   
int isTriangle(point a, point b)
{
    if(cmp(a.x, b.x) == 0)
	{
        return cmp(a.y, b.y);
    }
    return cmp(a.x, b.x);
}

/*int binSearch(int li, int ls, point A)
{
    if ( li <= ls )
    {
        int mid = ( li + ls ) / 2;
        int result = isTriangle ( p[mid], A );
        if (result == 0)
            return 1;
        else
            if (result < 0)
                return binSearch (mid + 1, ls, A);
            else
                return binSearch (li, mid-1, A);
 
    }
    else
        return 0;
}*/
int binSearch(point r) {
    int pos = 0;
    for(int i = 1<<30; i > 0; i >>= 1) {
		if(pos + i < n && isTriangle (p[pos + i], r) < 1) {
              pos += i;
         }
    }
       
	return isTriangle(r, p[pos]) == 0;
}

 
int compare (void const *a, void const *b)
{
    return ( *(double*)a - *(double*)b );
}

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

    fscanf(f, "%d", &n);
     
    for (int i = 0; i < n; i++)
        fscanf(f, "%lf %lf", &p[i].x, &p[i].y);
     
    qsort(p, n, sizeof(point), compare);
     
    point Q;
    int nrTriang = 0;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            Q = obt(p[i], p[j]);
            if (binSearch(Q) == 1);
                nrTriang++;
             
            Q = obt(p[j], p[i]);
            if ( binSearch(Q) == 1)
                nrTriang++;
        }
    }
    fprintf(g, "%d", nrTriang / 3);
    fclose(f); fclose(g);
    return 0;
}