z-garden

Can someone help me with the task, because it fails on every test case and when I test on first ,default test case it gives the right answer...
EDIT:Solved...

first of all i see, is :
n1 = tocka[ j ].y - tocka[ i ].y;
n1 /= tocka[ j ].x - tocka[ i ].x; ---> this
n2 = tocka[ j ].x * tocka[ i ].y - tocka[ i ].x * tocka[ j ].y;
n2 /= tocka[ j ].x - tocka[ i ].x; ---> and this

what if tocka[ j ].x == tocka[ i ].x ?? Then you are dividing with 0.

I know but what to do then, Can I multiply?

Something / 0 = infinite
Infinite can be replaced with very big constant number. So, if tocka[i].x=tocka[j].x, then n1/n2 should be something like 100000000000.

I've done it with Multiplication now but it fails on 4 and 13 test case:D

#include <cstdio>
#include <algorithm>
using namespace std;
struct tocke {
    int x,y;
}tocka[10000];
pair<int,int>nagib[1000000];

int main() {

    int apmax = 2, n , k = 0;
    scanf("%d",&n);

    for (int i = 0; i < n ; i++ ) {
        scanf("%d %d",  &tocka[ i ].x, &tocka[ i ].y);
    }

    int n1,n2;

    for (int i = 0 ; i < n ; i++) {
        for (int j = i+1 ; j < n ; j++) {
            n1 = tocka[ j ].y - tocka[ i ].y;
            n1 *= tocka[ j ].x - tocka[ i ].x;

            n2 = tocka[ j ].x * tocka[ i ].y - tocka[ i ].x * tocka[ j ].y;
            n2 *= tocka[ j ].x - tocka[ i ].x;

            nagib [ k ].first = n1;
            nagib [ k ].second = n2;
            k++;
        }

    }

    sort(nagib,nagib+k);

    int zb = 1;
    for (int i = 0 ; i <= k ; i++) {
        if ( nagib [ i + 1 ] == nagib [ i]) zb++;
        else
        zb = 1;
        apmax = max (zb,apmax);
    }

    printf("%d\n",apmax+1);


    return 0;
}

if it fails on time , try not to sort it , just run all combinations without sorting.

It doesn't fails on time it fails by WA!

use pair< double, double >

and then

for ( int i = 0; i < n; i++ )
        for ( int j = i+1; j < n; j++ )
        {
            double k1;
            double n1;
            if ( x[ i ] == x[ j ] )
            {
               k1 = INF;
               n1 = y[ i ];
            }
            else
            {
               k1 = ( y[ i ] - y[ j ] ) / double( x[ i ] - x[ j ] );
               n1 = y[ i ] - k1*x[ i ];
            }
            nagib[ k++ ] = make_pair( k1, n1 ) ;
        }

i think your code isn't working because of
a * b = b * a, so some clever cases fail.

i hope you understood me . :)

Thanks for help but it isn't working for any test case now here is the code

#include <cstdio>
#include <algorithm>
#define INF 99999999

using namespace std;
int x[ 10000 ];
int y[ 10000 ];
pair< double , double >nagib [ 500000 ];

int main() {

    int apmax = 0, n , k = 0;
    scanf("%d",&n);

    for (int i = 0; i < n ; i++ ) {
        scanf("%d %d",  &x[ i ], &y [ i ]);
    }



    for (int i = 0 ; i < n ; i++) {
        for (int j = i+1 ; j < n ; j++) {
            double k1,n1;
            if ( x [ i ] == x [ j ] ) {
                k1 = INF ;
                n1 = y [ i ];
            } else {
                k1 = (y[ i ] - y[ j ])  / double((x[ i ] - x[ j ]) );
                n1 =  (y[ i ] - k1 * x[ i ]);
                nagib [ k++ ] = make_pair( k1, n1 ) ;
            }

        }

    }

    sort(nagib,nagib+k);

    int zb = 1;
    for (int i = 1 ; i <= k ; i++) {
        if ( nagib [ i ] == nagib [ i - 1 ]) zb++;
        else
            zb = 1;
        apmax = max (zb,apmax);
    }

    printf("%d\n",apmax);

    return 0;

}

Any more ideas I tried with dividing and setting it to inf like Boris wrote but it fails for every test case then ...

you have mistake in your code:

you aren't adding new element to nagib if x[ i ] == x[ j ], and you should...


your code:

for (int i = 0 ; i < n ; i++) {
        for (int j = i+1 ; j < n ; j++) {
            double k1,n1;
            if ( x [ i ] == x [ j ] ) {
                k1 = INF ;
                n1 = y [ i ];
            } else {
                k1 = (y[ i ] - y[ j ])  / double((x[ i ] - x[ j ]) );
                n1 =  (y[ i ] - k1 * x[ i ]);
                nagib [ k++ ] = make_pair( k1, n1 ) ;
            }

        }

    }

should be:

for (int i = 0 ; i < n ; i++) {
        for (int j = i+1 ; j < n ; j++) {
            double k1,n1;
            if ( x [ i ] == x [ j ] ) {
                k1 = INF ;
                n1 = y [ i ];
            } else {
                k1 = (y[ i ] - y[ j ])  / double((x[ i ] - x[ j ]) );
                n1 =  (y[ i ] - k1 * x[ i ]);
           }
                nagib [ k++ ] = make_pair( k1, n1 ) ;

        }

    }

Well I pasted the wrong code but I tryed that and still no luck...

I don't know what to do anymore I tryed with comparing them using error as 0.00001 and rewriting formula but no luck... here is the code :D EDIT: CENSORED :D

This code

sort(nagib,nagib+k);
int zb = 1;
double raz1,raz2;
for (int i = 1 ; i < k ; i++) {
    raz1 = nagib [ i ].first - nagib [ i - 1 ].first;
    raz2 = nagib [ i ].second - nagib [ i - 1 ].second;
    if (fabs(raz1) < ERR  && fabs(raz2) < ERR ) zb++;
    else
        zb = 1;
    apmax = max (zb,apmax);
}

must be inside the for-i loop. Set k = 0 for each iteration, and the for-j loop should be for (int j = 0; j < n; j++) if (i != j)

But why? I am not testing every possible combination I am just testing if this equals last, and I sorted them first so they are fine?

Dgleich can you give me your mail... my code is similar to yours, so i'll send you my code, and you can see where your mistake is ?

ok thanks, my email is dominikgleich@hotmail.com

Solved thanks to Boris4 with this line of code but can someone explain what it does ?
:D
apmax = int ( (1 + sqrt ( 1 + 8 * apmax )) / 2);

oh, yea i can :)

well, if you have apmax... that is number of pairs of lines on one line...

for example if you have
4
0 0
0 1
0 2
0 3

you answer will be 6... ( all pairs )...
and now you have

x * ( x - 1 ) / 2 = apmax
and from there
x12 = ( 1 +- sqrt( 1 + 8 * apmax ) ) / 2

and you need x where sign is + :)
so you have
res = ( 1 + sqrt( 1 + 8 * apmax ) ) / 2;

i hope you understood me :)

oh I got it now, thanks...