Cod sursa(job #1417741)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 10 aprilie 2015 21:41:04
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define inFile "trapez.in"
#define outFile "trapez.out"
#define MAX_P 1001
#define MAX_L 500001
#define INF 1<<30
#define ERR 1e-7

FILE *in = fopen(inFile, "r");
FILE *out = fopen(outFile, "w");

struct Point {
    double x;
    double y;
};

struct Line {
    Point A;
    Point B;
    double Slope;
};

Point P[MAX_P];
Line L[MAX_L];

inline bool Equal(double A, double B);
inline bool Lesser(double A, double B);
inline double getSlope(Point A, Point B);
bool slopeSort(Line A, Line B);

int main() {
    int N, nLines = 0, i, j, nParralel;
    long long nTrapezoid = 0;
    
    fscanf(in, "%d", &N);
    for(i = 1; i <= N; i++) 
        fscanf(in, "%lf %lf", &P[i].x, &P[i].y);
        
    for(i = 1; i <= N; i++) {
        for(j = i+1; j <= N; j++) {
            ++nLines;
            L[nLines].A = P[i];
            L[nLines].B = P[j];
            L[nLines].Slope = getSlope(P[i], P[j]);
        }
    }
    
    sort(L+1, L+nLines+1, slopeSort);
    //for(i = 1; i <= nLines; i++) fprintf(out, "%f - %f ----- %f - %f ----- %f\n", L[i].A.x, L[i].A.y, L[i].B.x, L[i].B.y, L[i].Slope);
    for(i = 1; i <= nLines; ) {
        for(j = i; L[i].Slope == L[j].Slope; i++);
        nParralel = i-j;
        nTrapezoid += (nParralel * (nParralel - 1)) / 2;
    }
    
    fprintf(out, "%lld\n", nTrapezoid);
    
    fclose(in);
    fclose(out);
    
    return 0;
}

inline bool Equal(double A, double B) {
    return fabs(A-B) < ERR;
}

inline bool Lesser(double A, double B) {
    return B-A > ERR;
}

inline double getSlope(Point A, Point B) {
    if(A.x == B.x) return INF;
    return (B.y - A.y) / (B.x - A.x);
}

bool slopeSort(Line A, Line B) {
    return A.Slope < B.Slope;
}