Ура! Решил с длинной арифметикой.
eps = 0.0000000000000000000000000000000000000000000000000000000000000000001

Задача геометрически простая, но реализация в целой арифметике неприятная (ответ всё равно будет вещественный, но алгоритм можно сделать абсолютно точным при сравнении точек). Лучше использовать длинную вещественную арифметику.

Edited by author 06.08.2018 12:36

The same algo gives tl 4 in java ... In C++ I use vector of vectors for the capacity matrix as well as in java and the input is with the Scanner class . How can I optimize ? Thanks in advance.

#!python3
s = """0 30
-25.9807621135 -15
25.9807621135 -15
3.711537444785714 10.714285714285715
-11.134612334357143 -2.142857142857144
7.423074889571431 -8.571428571428571
18.557687223928568 23.57142857142857
-29.69229955828571 4.285714285714285
11.134612334357145 -27.857142857142854"""

import matplotlib.pyplot as plt
from math import cos, sin, pi
fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')

r=[[float(a) for a in p.split()] for p in s.split("\n")]
def d(a,b): return (r[a][0]-r[b][0])**2 + (r[a][1]-r[b][1])**2
def z(a,b): return abs(a-b) < 1e-6

a = 0
for i in range(len(r)):
    for j in range(i+1,len(r)):
        for k in range(j+1,len(r)):
            if z(d(i,j),d(i,k)) and z(d(i,j),d(j,k)) and z(d(j,k),d(i,k)):
                a += 1
                x = [r[t][0] + 0.5*cos(2*pi*a/9) for t in (i,j,k,i)]
                y = [r[t][1] + 0.5*sin(2*pi*a/9) for t in (i,j,k,i)]
                plt.plot(x, y, '-')
for p in r: plt.plot(p[0],p[1],'bo')
plt.grid()
plt.show()
print(a)

var
s:string;
m:array[-50000..50000]of char;
i,min,max,u:longint;

begin
readln(s);
u:=0;min:=90001;max:=-90001;

for i:=1 to length(s) do
  begin
   if s[i]='<' then dec(u);
   if u<1 then u:=1;
   if s[i]='>' then inc(u);
   if (s[i]<>'>')and(s[i]<>'<') then
                                begin
                                 m[u]:=s[i];
                                 if min>u then min:=u;
                                 if max<u then max:=u;
                                 inc(u);
                                end;
  end;

for i:=min to max do write(m[i]);

end.

can't pass TEST#7, just can't,,,,

A test which help me to discover a bug in my code:

5 1 4 1
1 2
2 4
4 5
3 5

Answer:
3
1 2 3

import numpy
n,m=input().split()
a=[]
for i in range(int(m)):
    a.append(int(input()))
b=numpy.zeros(int(n))
for i in range(int(n)):
    b[i]=a.count(i+1)/int(m)*100
    print('%.2f' % b[i]+'%')

Answer from system:Restricted function

Getting wa @ 14, can somebody please give me test cases for test 14?

don't use scanf("%d")

Edited by author 19.07.2014 21:19

要用高精度。。。long long只对10个点。。。

in addition to using manacher to find palindrome length, is there any data structure that needs to be used?

Если вы такой же идиот в геометрии, как и я, то сделайте 2 вложенных тернарных поиска по углам и все пройдет :).  Удачи

Some authors solved this problem with very good time and very small memory. But if we store input data without compressing it is necessary near 1Mb. Maybe there exist solution without storing input at all?
Who can help me to understand how it is possible?

Wa3 - answer is 0.00. there you should check the longest block ;)

I counted radius with precision 1e-10, upper bound is 1e6.
P.s. dont forget cases there center of circle is outside(like sample)

Statement lies: there are test cases when crosses needs two moves to win.

That pisses me off, because it's always a great challange to understand the right meaning of a statement, but this one just doesn't give you a chance to do that.

please give me some tests.All test that I found in other topic my programm pass.

I can't find mistake, help!!


#include <iostream>
#include <cmath>
using namespace std;
int main() {
    __int64 n,k;
    int s = 0;
    cin>>n>>k;
    int step;
    step = log(k)/log(2);
    if(n-pow(2,step+1)>=0) {
        n -= pow(2,step+1);
        s = (step+1)+ceil(n*1./k);
    } else {
        s = ceil(log(n)/log(2));
    }
    cout<<s;
}

just the rule of multiplication in combinatorics...

Formula:

ceil(log2(min(n, k))) + ceil((double)(n - (1 << (int)(ceil(log2(min(n, k))))))/ k)

Edited by author 29.07.2018 13:01

Edited by author 09.09.2018 17:50

This test helped me to get ac after wa16:
5
1 2
1 3
2 5
3 4