Mai intai trebuie sa te autentifici.

Cod sursa(job #333089)

Utilizator savimSerban Andrei Stan savim Data 21 iulie 2009 14:33:37
Problema Trapez Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

#define MAX_N 1024
#define cor 0.00000000001

int n, m, nr, sol;
struct punct {
    int x;
    int y;
} v[MAX_N];
long double A[MAX_N * MAX_N];

void cit() {
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &v[i].x, &v[i].y);
}

inline long double modul(long double x) {
    if (x >= 0) return x;
    else return -x;
}

void solve() {
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (v[i].y != v[j].y)
                A[++m] = 1.0 * (v[i].x - v[j].x) / (v[i].y - v[j].y);
            else A[++m] = 1.0 * 2147000000 * 1000;
            
    sort(A + 1, A + m + 1);
    
    int i = 1;

    while (i <= m) {
        int j = i;
        while (modul(A[j] - A[i]) < cor && j <= m)
            j++;
        if (j != i) j--;
        
        int nr = j - i + 1;
        
        sol = sol + nr * (nr - 1) / 2; 
        
        i = j + 1;
    } 
    
    printf("%d\n", sol);
}

int main() {

    cit();
    solve();

    return 0;
}