Use Manaker's algorithm

I've got WA 5 cause I checked that distance less than d only in case where Gnusmas is not on the border of the arc.

So, if you have WA#5 be careful with case where Gnusmas is on the border of the arc of fire.

Один и тот же алгоритм и практически один и тот же код,  с учётом схожести синтаксиса языков,  даёт :

AC 15 ms C++14 Clang

TLE #9 Python  2.7/3.4

But O(N^2 * logN) is death for python

Edited by author 23.08.2024 14:56

Edited by author 11.08.2025 18:30

Statement is unclear. If you want to solve it you must try all possible interpretations of this statement 'till find the one that the author intended.

These tests helped me to fix WA8

10
4811511
2282103
4376795
8402551
3861207
8577438
2810768
5559695
8993319
5240873

infinity

10
9706784
5106148
5528237
9514430
1047500
6715041
9514430
7524350
4524591
2186600

infinity

But then I had WA27, which I fixed by ignoring number 1 somewhere in my code, and got AC.

But my AC solution is still wrong, here is the test breaking it (upd: my second AC code passes it):
10
8246707
8246707
6566521
3418657
9048372
2505801
428602
9261803
4761595
6564437

Correct answer:
2
My AC code output:
infinity

Edited by author 20.08.2024 19:31

#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;
}

Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память?

Precision problem: try rounding intersection points or using epsilon when comparing points.

brute force

Edited by author 18.08.2024 01:04

Problem is almost equal to 1203, there is really trivial solution if you now how to solve 1203.

But rating of this problem is 711 and of 1203 is 82. It's strange)

Just bruteforce

First 8 tests all cords are from -1000 to 1000, maybe it can help somebody)