In the measurements it is written that when 1 response 1 2 3. But in the condition said "If there are several solutions, display, where a minimum. If such multiple, display, where the minimum of b and so on". So the correct answer should be 1 1 2.

(В промерах написано, что при 1 ответ 1 2 3. Но в условии сказано "Если решений несколько, вывести то, где a минимально. Если и таких несколько, вывести то, где минимально b и т.д". Поэтому правильный ответ должен быть 1 1 2.)

Edited by author 09.11.2014 17:33

In my solution, it was a bug with precision. So I fixed it, by using int instead of double, as much as it was possible

sys.setrecursionlimit(10**9) + python instead of PyPy

Test:

1 4
m
m a
a b
b c
c a

Output:
-1

How I can check the tests?

Use BFS, use bitset, use binsearch, use random shuffle and get easy AC!

The description of the problem says: "Your program must take into account the command \", which is used to write two dots above a vowel. For example, \"e means the symbol ë." But you don't really have to distinguish between vowels and consonants for this command.

Edited by author 26.08.2024 17:37

My program use iostream for reading data. Always when i use iostream i add this lines to turn off flushing after each line:

signed main(void) {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    // solution
    return 0;
}

But in this problem program with this lines getting WA#1, without - AC. Why?

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

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

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

brute force