Cod sursa(job #216931)

Utilizator MciprianMMciprianM MciprianM Data 26 octombrie 2008 10:37:41
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<fstream>
#include<cstdlib>
using namespace std;
struct punct{
   int x,y;
};
punct a[1001];
int p1[500501];
int p2[500501];
int n,np;
int nR(int st,int dr){

  double x1=p1[st];
  if(p2[st])  x1=x1/p2[st];
  else {
    if(p2[dr]) return 1;
    else return 0;
  }

  double x2=p1[dr];
  if(p2[dr]) x2=x2/p2[dr];
  else return 0;

  if(x1>x2)  return 1;
  else return 0;
}
int part(int st,int dr){
  int ii, jj, aux;
  ii=0;jj=-1;
  while(st<dr){
    if(nR(st,dr)){
      aux=-ii;
      ii=-jj;
      jj=aux;
      aux=p1[st];p1[st]=p1[dr];p1[dr]=aux;
      aux=p2[st];p2[st]=p2[dr];p2[dr]=aux;
    }
    st+=ii;dr+=jj;
  }
  return st;
}
void sorteaza(int st,int dr){
  if(st<dr){
    int r=random()%(dr-st+1);
    r=st+r;
    int aux;
    aux=p1[r];p1[r]=p1[st];p1[st]=aux;
    aux=p2[r];p2[r]=p2[st];p2[st]=aux;
    int m=part(st,dr);
    sorteaza(st,m-1);
    sorteaza(m+1,dr);
  }
}
int main(){
  int i,j;
  ifstream f("trapez.in");
  f>>n;
  for(i=0;i<n;i++)
    f>>a[i].x>>a[i].y;
  f.close();
  for(i=0;i<n;i++)
    for(j=i+1;j<n;j++){
        p1[np]=a[i].y-a[j].y;
        p2[np]=a[i].x-a[j].x;
        np++;
    }
  sorteaza(0,np-1);
  int rasp=0;
  int comp1=p1[0],comp2=p2[0],k=1;
  for(i=1;i<np;i++){
    if(comp1*p2[i]==comp2*p1[i])  k++;
    else{
      rasp+=(k*(k-1)/2);
      comp1=p1[i];comp2=p2[i];
      k=1;
    }
  }
  ofstream g("trapez.out");
  g<<rasp<<'\n';
  g.close();
  return 0;
}