Cod sursa(job #979766)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 2 august 2013 18:34:46
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#define epsilon 0.00000000001
#define nmax 1005
#define inf 1<<30
using namespace std;
 
int n, sol, egale;
int x[nmax], y[nmax];
 
vector <double> p;
 
bool cmp(double a, double b) {
    return (a<b);
}
 
 
int main() {
    ifstream f("trapez.in");
    ofstream g("trapez.out");
 
    f>>n;
    for(int i=1; i<=n; i++) f>>x[i]>>y[i];
 
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++) {
            //if(y[i] == y[j]) p.push_back(double(inf));
            p.push_back( double(y[j] - y[i]) / (x[j] - x[i]) );
        }
 
    sort(p.begin(), p.end(), cmp);
 
    //for(int i=0; i<p.size(); i++) cout<<p[i]<<"\n";
 
    for(int i=0, j=0; i<p.size() && j+1<p.size(); ) {
        j = i;
        egale = 1;
        while(j+1 < p.size() && p[j+1] - p[j] < epsilon) egale++, j++;
 
        //cout<<"p[i] = "<<p[i]<<" si p[j] = "<<p[j]<<" si egale = "<<egale<<"\n";
 
        sol += (egale * (egale-1)) / 2;
 
        i = j+1;
    }
 
    g<<sol<<"\n";
 
    return 0;
}