Pagini recente » Cod sursa (job #836883) | Cod sursa (job #3192866) | Cod sursa (job #2631479) | Cod sursa (job #431630) | Cod sursa (job #2072657)
#include <bits/stdc++.h>
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");
int const INF=2e9;
double const eps=1e-10;
struct point{
int x, y;
}puncte[1001];
struct fractie{
int a, b;
}temp;
struct dreapta{
fractie panta;
int c;
}drepte[500001];
int cmmdc(int a, int b){
if (b==0)
return a;
return cmmdc(b, a%b);
}
bool cmp(dreapta a, dreapta b){
if (1.0*a.panta.a/a.panta.b<1.0*b.panta.a/b.panta.b) return true;
else if (1.0*a.panta.a/a.panta.b==1.0*b.panta.a/b.panta.b)
if (a.c<=b.c) return true;
return false;
}
int main(){
int n, i, j, lv=0, dx, dy, cmm, sti, li, dscz, trapeze=0;
in >> n;
for (i=1; i<=n; i++)
in >> puncte[i].x >> puncte[i].y;
for (i=1; i<=n; i++)
for (j=i+1; j<=n; j++){
lv++;
dx=puncte[j].x-puncte[i].x;
dy=puncte[j].y-puncte[i].y;
cmm=cmmdc(dx, dy);
dx/=cmm;
dy/=cmm;
if (dx)
temp={dy, dx};
else
temp={INF, 1};
drepte[lv].panta = temp;
drepte[lv].c=puncte[i].x*dy -puncte[i].y*dx;
}
sort(drepte+1, drepte+lv+1, cmp);
drepte[lv+1]={{INF, INF}, INF};
// for (i=1; i<=lv; i++)
// cout << drepte[i].panta.a << ' ' << drepte[i].panta.b << ' '<< drepte[i].c << endl;
for (i=1; i<=lv; i++){
sti=i;
dscz=0;
while (i<=lv && drepte[i].panta.a==drepte[i+1].panta.a && drepte[i].panta.b==drepte[i+1].panta.b){ ///cat timp sunt paralele
li=i;
while (i<=lv && drepte[i].c==drepte[i+1].c) i++; ///cat timp sunt identice
dscz+=(i-li+1)*(i-li)/2;
if (drepte[i].panta.a==drepte[i+1].panta.a && drepte[i].panta.b==drepte[i+1].panta.b) i++;
}
trapeze+=(i-sti+1)*(i-sti)/2-dscz;
}
out << trapeze;
}