Cod sursa(job #220965)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 13 noiembrie 2008 21:34:43
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("trapez.in");
ofstream fout ("trapez.out");

struct punct
{
     int x,y;
     float p;
};
punct sir[1010],pant[101010];
int n,nr;

void citire()
{
     fin>>n;
     for (int i=0;i<n;i++)
          fin>>sir[i].x>>sir[i].y;
}

bool operator<(punct a,punct b)
{
     return a.p<b.p;
}

float panta(punct a,punct b)
{
     if (a.x==b.x)
          return 1000000;
     return (float)(a.y-b.y)/(a.x-b.x);
}

void creare()
{
     nr=0;
     for (int i=0;i<n-1;i++)
          for (int j=i+1;j<n;j++)
          {
               if (sir[i].x>sir[j].x)
               {
                    pant[nr].y=sir[i].y-sir[j].y;
                    pant[nr].x=sir[i].x-sir[j].x;
                    pant[nr++].p=panta(sir[i],sir[j]);
               }
               else
               {
                    pant[nr].y=sir[j].y-sir[i].y;
                    pant[nr].x=sir[j].x-sir[i].x;
                    pant[nr++].p=panta(sir[j],sir[i]);
               }
          }
          sort(pant,pant+nr);
}

void numara()
{
     long numar=0,aux=1,nr_p=0;
     for (int i=1;i<nr;i++)
     {
          if (pant[i].x*pant[i-1].y==pant[i].y*pant[i-1].x)
          {
               aux++;
               if (pant[i].p-pant[i-1].p<0.000001)
                    nr_p++;
          }
          else
          {
               if (aux!=1)
               {
                    long P=1;
                    P=(aux-1)*aux/2;
                    numar+=P;
               }
               aux=1;
          }
     }
     if (aux!=1)
     {
          long P=1;
          P=(aux-1)*aux/2;
          numar+=P;
     }
     fout<<numar-nr_p/2<<"\n";
}


int main ()
{
     citire();
     creare();
     numara();
     return 0;
}