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

Edited by author 18.08.2024 01:04

Just bruteforce

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

#include<iostream>

using namespace std;
 int main() {
 string s;
 cin >> s;
 for(auto now : s) cout << 1;
}

Edited by author 14.01.2026 22:14

How to do without palindromic tree???