Cod sursa(job #2843124)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 2 februarie 2022 01:05:58
Problema Trapez Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define NMAX 1001
#define SOLMAX 500001

int x[NMAX];
int y[NMAX];

struct fractie {
    int sus;
    int jos;
};

fractie panta[SOLMAX];

bool cmp(fractie i, fractie j) {
    return (i.sus*j.jos > i.jos*j.sus);
}


int main() {
    FILE *fin, *fout;
    fin = fopen("trapez.in", "r");
    fout = fopen("trapez.out", "w");
    
    int n, i, j, nr, nra, nrtot, nra0;
    
    fscanf(fin, "%d", &n);
    
    for (i=0; i<n; i++) {
        fscanf(fin, "%d%d", &x[i], &y[i]);
    }
    
    nr = 0;
    for (i=0; i<n-1; i++) {
        for (j=i+1; j<n; j++){
            panta[nr].sus = y[j]-y[i];
            panta[nr].jos = x[j]-x[i];
            nr++;
        }
    }
    
    sort(panta, panta+n*(n-1)/2, cmp);
    
    nrtot = 0;
    nra = 1;
    nra0 = 1;
    for (i=1; i<nr; i++) {
        if (panta[i].sus*panta[i].jos==0 && panta[i-1].sus*panta[i-1].jos==0) {
            if ((panta[i].sus==0 && panta[i-1].sus==0) || (panta[i].jos==0 && panta[i-1].jos==0)) {
                nra0++;
            } else {
                nrtot += nra0*(nra0-1)/2;
            }
        } else {
            if (panta[i].sus*panta[i-1].jos == panta[i].jos*panta[i-1].sus) {
                nra++;
                nra0++;
            } else {
                nrtot += nra*(nra-1)/2;
                nra = 1;
            }
        }
    }
    
    fprintf(fout, "%d\n", nrtot);
    
    fclose(fin);
    fclose(fout);
    return 0;
}