Cod sursa(job #22957)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 27 februarie 2007 21:06:25
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>
#include<stdlib.h>

int n, k, contor;
struct nod1 {int x, y;} p[1010];
struct nod2 {int s, j;} seg[1000010];

int comp(const void *i, const void *j)
{
  nod2 *ei= (nod2*)i,
       *ej= (nod2*)j;

  return ei->s* ej->j - ei->j * ej->s;
}

void solve()
{
//  for(int i=1; i<=k; ++i) printf("%d %d\n",seg[i].s, seg[i].j);
//  printf("\n");


  freopen("trapez.out","w",stdout);

  int i, j;
  for(i=1; i<=k; i++) {
//   for(j=i+1; j<=k && seg[i].s* seg[j].j == seg[i].j * seg[j].s; ++j) contor++;
     for(j=i+1; j<=k; ++j) if(seg[i].s* seg[j].j == seg[i].j * seg[j].s) contor++;
   
  }
  printf("%d\n",contor);
  
}

int main()
{
  freopen("trapez.in","r",stdin);
  scanf("%d",&n);

  int pox=0, poy=0;
  
  for(int i=1; i<=n; ++i) scanf("%d %d",&p[i].x, &p[i].y);
  for(int i=1; i<=n-1; ++i)
    for(int j=i+1; j<=n; ++j) {
    
      seg[++k].s= p[i].y- p[j].y;
      seg[k].j= p[i].x- p[j].x;

      if( seg[k].s<0 && seg[k].j<0) seg[k].s*=-1, seg[k].j*=-1;
      else if( seg[k].s>0 && seg[k].j<0) seg[k].s*=-1, seg[k].j*=-1;
      
      if( seg[k].s==0 ) { pox++; k--; }
      else if( seg[k].j==0) {poy++; k--; }
    }
  for(int i=1; i<=pox-1; ++i) contor+=i;
  for(int i=1; i<=poy-1; ++i) contor+=i;

//printf("PP%d %d",pox,poy);

  qsort(seg+1, k, sizeof(nod2), comp);
  solve();
    
  
  return 0;
}