Cod sursa(job #4419)

Utilizator vlad_DVlad Dumitriu vlad_D Data 3 ianuarie 2007 05:38:30
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
/*

#INFOARENAAA
*/
#include <stdio.h>
#include <math.h>
int n, sol = 0;
double eps = 0.001;
struct point {double x, y;};
point v[1600];
void read_in() {
     freopen("triang.in", "r", stdin);
     scanf("%d", &n);
     for (int i=1; i<=n; i++) scanf("%lf %lf", &(v[i].x), &(v[i].y));
     fclose(stdin);
     }
double dist(point A, point B) {
       return 3.0/4.0*((A.x-B.x)*(A.x-B.x) + (A.y - B.y)*(A.y - B.y));
       }
point solve( double M, double D) {
       point ret;
       ret.x = sqrt(D / (M*M + 1));
       ret.y = M*ret.x;
       return ret;
       }
double abs(double A) {
       if (A < 0) return -A;
       return A;
       }
void print_out() {
     freopen("triang.out", "w", stdout);
     printf("%d\n", sol);
     fclose(stdout);
     }
int k, l ,r, pasi=0;
int mai_mic(point A, point B) {
    if (A.x > B.x) return 1;
    if (A.x == B.x && A.y > B.y) return 1;
    return 0;
    }
int partite(int p, int r) {
    point x = v[p];
    int i = p - 1, j= r+1;
    while (1) {
          do {j--; } while (mai_mic(v[j], x));
          do {i++;} while (mai_mic(x, v[i]));
          if (i < j) {point aux = v[i]; v[i] = v[j]; v[j] = aux;}
          else return j;
          }
    }
void qsort(int p, int r) {
     if (p < r) {
        int q = partite(p ,r);
        qsort(p, q);
        qsort(q+1, r);
        }
     }
int main() {
read_in();
int i, j;
//hai sa le sortam
qsort(1, n);
for (i=1; i<=n; i++)
    for (j=i+1; j<=n; j++) {
        double M;
        point middle, raise, p;
        middle.x = v[i].x + v[j].x; middle.x/=2;
        middle.y = v[i].y + v[j].y; middle.y/=2;
        if (abs(v[i].y - v[j].y)<eps) {
           raise.x = 0; raise.y = sqrt(dist(v[i], v[j]));
           }
        else {
        M =-(v[i].x - v[j].x)/(v[i].y - v[j].y);
        raise = solve(M, dist(v[i], v[j]));}
        int gasit = 0;
        p.x = middle.x + raise.x;
        p.y = middle.y + raise.y;
        l = j ; r = n;
        if (!(p.x > v[n].x+eps))
        while (l<=r) {
             k = l +r; k>>=1;
              if (abs(v[k].x - p.x) < eps) {
              if( abs(v[k].y - p.y) < eps) {gasit = 1; break;}
                 if (p.y  > v[k].y) l = k + 1;
                 else r = k - 1;
                 }
              else {if (p.x  > v[k].x) l= k+1; else r = k-1;}
              }

        //cauta binar si pune gasit = 1 daca gasesti
        sol+=gasit; gasit = 0;
        raise.x*=-1; raise.y*=-1;
        p.x = middle.x + raise.x;
        p.y = middle.y + raise.y;
        l = j ; r = n;
        pasi=0;
        if ( ! (p.x > v[n].x+eps))
        while (l<=r) {
              k = l +r; k>>=1;

              if (abs(v[k].x - p.x) < eps) {
              if( abs(v[k].y - p.y) < eps) {gasit = 1; break;}
                 if (p.y  > v[k].y) l = k + 1;
                 else r = k - 1;
                 }
              else {if (p.x > v[k].x) l= k +1; else r = k-1;}
              }


        //cauta binar si pune gasit =1 daca gasesti
        sol+=gasit;
        }
print_out();
return 0;
}