Cod sursa(job #382122)

Utilizator vladiiIonescu Vlad vladii Data 12 ianuarie 2010 21:51:19
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <iostream>
#include <fstream>
#include <math.h>
//#include <conio.h>
using namespace std;

#define e 0.00001

int N;
struct Pct {
    double x;
    double y;
} vec[1501];

int cmp(Pct a, Pct b) {
    if(a.x!=b.x) { return a.x<b.x; }
    return a.y<b.y;
}

int CBinar(double x, double y, int poz) {
    int ls=0, ld=N-1, mij;
    while(ls<=ld) {
         if(ld<poz) { return 0; }
         mij=ld+(ls-ld)/2;
         if(-e<vec[mij].x-x && vec[mij].x-x<e && -e<vec[mij].x-x && vec[mij].y-y<e) {
              return mij;
         }
         else if(vec[mij].x<x) {
              //caut in dreapta
              ls=mij+1;
         }
         else if(vec[mij].x>x) {
              //caut in stinga
              ld=mij-1;
         }
         else if(vec[mij].x==x && vec[mij].y<y) {
              ls=mij+1;
         }
         else if(vec[mij].x==x && vec[mij].y>y) {
              ld=mij-1;
         }
    }
    return 0;
}

int main() {
    FILE *f1=fopen("triang.in", "r"), *f2=fopen("triang.out", "w");
    int i, j, nr=0, la, lu;
    double p, q, x, y, z;
    double a, b, c, d;
    double aux1, aux2, aux3, del, rad, y1, y2, x1, x2;
    fscanf(f1, "%d", &N);
    for(i=0; i<N; i++) {
         fscanf(f1, "%lf%lf", &vec[i].x, &vec[i].y);
    }
    sort(vec, vec+N, cmp);
    for(i=0; i<N; i++) {
         for(j=i+1; j<N; j++) {
              a = vec[i].x; b = vec[i].y;
              c = vec[j].x; d = vec[j].y;
              if(a-c!=0 && b-d!=0) {
                   p=2*(a-c);
                   p=(a+c)/2 + (b+d)*(b-d)/p;
                   q=(b-d)/(a-c);
                   //x+q*y=p
                   z = c*c - 2*a*c + d*d - 2*b*d;
                   aux1 = q*q + 1;
                   aux2 = 2*a*q - 2*b - 2*p*q;
                   aux3 = p*p - 2*a*p - z;
                   //aux1 * y^2 + aux2 * y + aux3 = 0
                   del=aux2*aux2 - 4*aux1*aux3;
                   del=sqrt(del);
                   if(-e<(-aux2-del) && (-aux2-del)<e) { y1=0; } 
                   else { y1=(-aux2-del)/(2*aux1); }
                   if(-e<(p-q*y1) && (p-q*y1)<e) { x1=0; }
                   else { x1=p-q*y1; }
                   if(-e<(del-aux2) && (del-aux2)<e) { y2=0; }
                   else { y2=(-aux2+del)/(2*aux1); }
                   if(-e<(p-q*y2) && (p-q*y2)<e) { x2=0; }
                   else { x2=p-q*y2; }
              }
              else if(b-d==0) {
                   x1=x2=(a+c)/2;
                   aux1=1;
                   aux2=-2*b;
                   aux3=(c-a)*(c-a)/4 + b*b - (a-c)*(a-c);
                   del=aux2*aux2 - 4*aux1*aux3;
                   del=sqrt(del);
                   if(-e<(-aux2-del) && (-aux2-del)<e) { y1=0; } 
                   else { y1=(-aux2-del)/(2*aux1); }
                   if(-e<(del-aux2) && (del-aux2)<e) { y2=0; }
                   else { y2=(-aux2+del)/(2*aux1); }   
              }
              else if(a-c==0) {
                   y1=y2=(b+d)/2;
                   aux1=1;
                   aux2=-2*c;
                   aux3=(b-d)*(b-d)/4 + c*c - (b-d)*(b-d);
                   del=aux2*aux2 - 4*aux1*aux3;
                   del=sqrt(del);
                   if(-e<(-aux2-del) && (-aux2-del)<e) { y1=0; } 
                   else { x1=(-aux2-del)/(2*aux1); }
                   if(-e<(del-aux2) && (del-aux2)<e) { y2=0; }
                   else { x2=(-aux2+del)/(2*aux1); }
              }
              la=CBinar(x1, y1, j);
              lu=CBinar(x2, y2, j);
              //cout<<"i="<<i<<" , j="<<j<<endl;
              //cout<<x1<<" "<<y1<<endl;
              //cout<<x2<<" "<<y2<<endl;
              //cout<<la<<", "<<lu<<endl;
              //cout<<endl;
              if(la && la>j) { nr++; }
              if(lu && lu>j) { nr++; }
         }
    }
    fprintf(f2, "%d\n", nr);
    fclose(f1); fclose(f2);
    //getch();
    return 0;
}