I coded O(n^3) that was accepted fairly easy... But I know there is O(n^2) algo but I don't know how to implement it.. Any Ideas?

does anyone know what is this test?
thanks

n^3 is suitable for which n<=200
but pay attention to the collinear problem

Edited by author 17.05.2019 14:43

И все же...
Что там за набор такой?

6
0 3
0 0
3 0
0 3
1 2
2 1

answer 5 (0 0 is not)

16
15 15
16 17
17 19
18 21
19 23
75 19
16 62
13 69
10 76
7 83
4 90
1 97
-2 104
-5 111
-8 118
-11 125

answer: 10 (last 10)

13
1 1
1 1
1 1
16 62
13 69
10 76
7 83
4 90
1 97
-2 104
-5 111
-8 118
-11 125

answer: 10 (last 10 your program could get 10 in prev test and get 13 here)


8
1 1
1 1
1 1
0 0
0 0
0 0
0 0
2 2

answer 8

5
4 4
4 4
4 4
4 4
4 4

answer 5

I hope, it will help you (P.S. you can click on my nickname and write me, i with big pleasure help you)

Edited by author 03.03.2017 22:18

I solved it in 0.015 with g++, but i can't optimize anymore

Edited by author 22.06.2015 13:32

What's on test 6? help, please!

#include <cstdio>
#include <vector>
#include <math.h>
#include <cstdlib>
#include <algorithm>
using namespace std;
double line_k(double x1, double y1, double x2, double y2)
{
    double k = (y2 - y1)/(x2 - x1);
    return k;
}
double line_b(double x1, double y1, double x2, double y2)
{
    double b = y2 - (y2 - y1) * x2 / (x2 - x1);
    return b;
}
bool is_on_line(double k, double b, double x, double y)
{
    if (y <= x * k + b + 0.01 && y >= x * k + b - 0.01) return true;
    return false;
}
struct point{
    double x,y;
};
int main()
{
    int n, counter = 2, max_zerosx = 0, max_zerosy = 0;
    double x, y, k, b;
    vector <point> koord;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf %lf", &x, &y);
        if (x == 0) max_zerosx++;
        if (y == 0) max_zerosy++;
        {
            koord.push_back(point());
            koord[i].x = x;
            koord[i].y = y;
        }
    }
    int maximal = max(max_zerosx, max_zerosy);
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            k = line_k(koord[i].x, koord[i].y, koord[j].x, koord[j].y);
            b = line_b(koord[i].x, koord[i].y, koord[j].x, koord[j].y);
            for (int l = j + 1; l < n; l++)
                 if (is_on_line(k, b, koord[l].x, koord[l].y))
                     counter++;
            if (counter > maximal) maximal = counter;
            counter = 2;
        }
    }
    printf("%d", maximal);
    return 0;
}

what's test2? my program has passed test 1 and 3 as i know
thx

Not understand the algorithm. What is it? Please explain the problem.

Some new tests were added. 234 authors lost AC. Maybe we'll add more tests soon.

Edited by author 25.03.2012 18:41

In my solution I read values like this:

        scanf("%d %d", &px[i], &py[i]);
        px[i] += 1000;
        py[i] += 1000;
        board[px[i]][py[i]] = 1;

and get access violation on test #4; however, if I add right before accessing the array:

        if (px[i] < 0 || py [i] < 0 || px[i] > 2000 || py[i] > 2000) {
            while (1);
        }

I get TLE on the same test.

Are all the values of test #4 within the bounds -1000 <= x,y <= 1000 ?!

I have understood why you could have some strange WA2.
my program:

while (scanf("%d", &n) >= 1) {
    ...


}
if I write
while (scanf("%d", &n) >= 1) {
     if (!n)
        break;
    ...


}
I'll get AC..(though n >= 2=))
they have some trash at the end of the file...

Edited by author 11.08.2011 18:49

What test6? please help me.

Edited by author 12.05.2011 11:10

if (pts[m].y == (int)(Math.Round(k * (double)pts[m].x + b)))

this i changed on

if (Math.Abs(pts[m].y - (k * (double)pts[m].x + b))<0.000000001)

and now I have AC

Edited by author 08.01.2010 03:08