Cod sursa(job #3229102)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 13 mai 2024 20:31:36
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
/*#include <bits/stdc++.h>
using namespace std;
ifstream f("trapez.in");
ofstream g("trapez.out");
struct punct {int x;int y;}v[1002],a;
map<punct,int> M;
int n,i,j,sus,jos,nr1,nr2,cmmdc,sol;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)f>>v[i].x>>v[i].y;

    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
        {   sus = v[i].y - v[j].y;
            jos = v[i].x - v[j].x;
            if (jos==0)nr1++;
            else if (sus==0)nr2++;
            else{
                cmmdc=__gcd(abs(sus),abs(jos));
                sus/=cmmdc;
                jos/=cmmdc;
                if (sus<0&&jos<0)sus=-sus,jos=-jos;
                else if (sus>0&&jos<0)sus=-sus,jos=-jos;
                a={sus,jos};
                M[a]++;
            }

        }
    for (auto it:M)
    {   sol+=it.second*(it.second-1)/2;
        cout<<it.first.x<<' '<<it.first.y<<' '<<it.second<<'\n';
    }
    sol+=nr1*(nr1-1)/2+nr2*(nr2-1)/2;
    g<<sol<<'\n';
    return 0;
}*/
#include <bits/stdc++.h>
using namespace std;
ifstream f("trapez.in");
ofstream g("trapez.out");
struct punct {int x;int y;}v[1002],a;
struct pct {int sus;int jos;}V[1000004];
int n,i,j,sus,jos,nr1,nr2,cmmdc,sol,k;
bool mycmp(pct a, pct b)
{   if (a.sus>0&&b.sus>0)return a.sus*b.jos<b.sus*a.jos;
    if (a.sus<0&&b.sus<0)return a.sus*b.jos>b.sus*a.jos;
    return a.sus<0;

}
int main()
{
    f>>n;
    for (i=1;i<=n;i++)f>>v[i].x>>v[i].y;

    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
        {   sus = v[i].y - v[j].y;
            jos = v[i].x - v[j].x;
            if (jos==0)nr1++;
            else if (sus==0)nr2++;
            else{
                cmmdc=__gcd(abs(sus),abs(jos));
                sus/=cmmdc;
                jos/=cmmdc;
                if (sus<0&&jos<0)sus=-sus,jos=-jos;
                else if (sus>0&&jos<0)sus=-sus,jos=-jos;
                V[++k]={sus,jos};
            }

        }
    sort(V+1,V+1+k,mycmp);

    sol+=nr1*(nr1-1)/2+nr2*(nr2-1)/2;
    nr1=1;
    for (i=2;i<=k;i++)
    {
        if (V[i].sus==V[i-1].sus&&V[i].jos==V[i-1].jos)
        {   nr1++;

        }
        else {
            sol+=(nr1-1)*nr1/2;
            nr1=1;
        }
    }
    sol+=nr1*(nr1-1)/2;
    g<<sol<<'\n';
    return 0;
}