Cod sursa(job #1081218)

Utilizator impulseBagu Alexandru impulse Data 13 ianuarie 2014 13:06:15
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
//
//  main.cpp
//  trapez
//
//  Created by Alexandru Bâgu on 1/13/14.
//  Copyright (c) 2014 Alexandru Bâgu. All rights reserved.
//

#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;
typedef struct {
    int x, y;
} coord;
typedef struct {
    coord a, b;
    double m; //m = (Yb - Ya) / (Xb - Xa)
} line;
double slope(coord a, coord b)
{
    return (double)(b.y - a.y) / (double)(b.x - a.x);
}
int cmp(line a, line b) { return a.m <= b.m; }
int main(int argc, const char * argv[])
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);
    int n;
    scanf("%d", &n);
    coord* C = new coord[n];
    int i, j, tx = 0, q;
    for(i = 0; i < n; i++)
        scanf("%d %d", &C[i].x, &C[i].y);
    line* L = new line[n * n];
    for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            L[tx].a = C[i];
            L[tx].b = C[j];
            L[tx].m = slope(C[i], C[j]);
            tx++;
        }
    }
    sort(L, L + tx, cmp);
    int tr = 0;
    i = 0;
    while (i < tx)
    {
        j = i;
        while(j < tx && L[i].m == L[j].m) j++;
        q = j - i - 1;
        tr += q + (q -1) / 2;
        i = j;
    }
    printf("%d", tr);
    return 0;
}