Cod sursa(job #1229122)

Utilizator thinkphpAdrian Statescu thinkphp Data 16 septembrie 2014 15:32:01
Problema Trapez Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>
#define MAX 1002 
#define max 1000001

FILE *fin, *fout;

struct Point {
       int x;
       int y;  
};

struct Point P[ MAX ];

int N;

long sum = 0;

double arr[ max ];

//function prototypes
void read(const char*);
void solve();
double incline(struct Point, struct Point);
void quicks(int,int);
int getPos(int,int); 
void write(const char*);

int main() {
 
    read("trapez.in");

    solve();

    write("trapez.out");

  return 0;
};

void read(const char* filename) {

     int i;

     fin = fopen(filename, "r");

     fscanf(fin, "%d", &N);

     for(i = 1; i <= N; i++) {

         fscanf(fin, "%d %d", &P[ i ].x, &P[ i ].y);
     }

     fclose( fin ); 
};

void solve() {

     int i, j, k = -1;

     int n = 1;

     for(i = 1; i < N; i++) {

         for(j = i + 1; j <= N; j++) {
               
             arr[ ++k ] = incline( P[ i ], P[ j ] );
         }     
     }

     quicks(0,k);

     //for(i = 0; i <= k;i++) printf("%.2f ", arr[ i ]);
    
     for(i=1;i<=k;i++)
 
         if(arr[ i ] == arr[i - 1]) n++;

                   else sum += (long) ((n * (n - 1)) / 2), n = 1;
};

double incline(struct Point p1, struct Point p2) {

       if((p2.x - p1.x) != 0) return (double) (p2.y - p1.y) / (p2.x - p1.x); 

                         else return 0x3f3f3f3f;
};

int pivot(int li, int ls) {

    int i,j,i1,j1;
    i = li;
    j = ls;
    double aux;
    i1 = 0;
    j1 = -1;

    while(i < j ) {

          if( arr[ i ] > arr[ j ] ) {

             aux = arr[ i ];
             arr[ i ] = arr[ j ];
             arr[ j ] = aux;
             
             aux = i1;
             i1 = -j1;
             j1 = -aux;
          }

          i = i + i1;
          j = j + j1; 
    }

    return i;   
};

void quicks(int li, int ls) {

     int posPivot;

     if( li < ls ) {

        posPivot = pivot(li,ls);

        quicks(li,posPivot-1);

        quicks(posPivot+1,ls);
     }
};

void write(const char *filename) {

     fout = fopen(filename, "w");

     fprintf(fout, "%d", sum);

     fclose( fout );
}