Cod sursa(job #1095843)

Utilizator IronWingVlad Paunescu IronWing Data 1 februarie 2014 00:37:17
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
/* 
 * File:   trapez.cpp
 * Author: Vlad
 *
 * Created on January 31, 2014, 11:37 PM
 */

#include <cstdio>
#include <algorithm>

using namespace std;

typedef struct _point {
    float x, y;
} Point;

int n;
int verticalSlopesCount;
Point p[1002];

int computeSlopes(float slopes[]) {
    verticalSlopesCount = 0;
    int idx = 0;
    for (int i = 1; i < n; i++) {
        Point *p1 = p + i;
        for (int j = i + 1; j <= n; j++) {
            if (p1->x != p[j].x) {
                slopes[idx++] = (p[j].y - p1->y) / (p[j].x - p1->x);
            } else verticalSlopesCount++;
        }
    }
    return idx;
}

int main(int argc, char** argv) {

    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%f %f", &p[i].x, &p[i].y);
    }

    // combinari de n luate cate 2
    float *slopes = new float[n / 2 * (n - 1)];

    int total = computeSlopes(slopes);
    sort(slopes, slopes + total);


    int trapeze = verticalSlopesCount / 2 * (verticalSlopesCount - 1);
    int equal = 1;
    for (int i = 0; i < total - 1; ++i) {
        if (slopes[i + 1] - slopes[i] < 0.00001) equal++;
        else {
            // combinari de n luate cate 2
            trapeze += (equal / 2 * (equal - 1));
            equal = 1;
        }
    }

    trapeze += (equal / 2 * (equal - 1));

    printf("%d\n", trapeze);
    delete[] slopes;
    return 0;
}