QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#793556	#9804. Guess the Polygon	LittleXi^#	AC ✓	90ms	11808kb	Python3	3.6kb	2024-11-29 21:04:40	2024-11-30 11:51:17

Judging History

This is the latest submission verdict.

[2024-11-30 11:51:17]
管理员手动重测本题所有提交记录

Verdict: AC
Time: 90ms
Memory: 11808kb

Show

[2024-11-29 21:04:40]
Judged

Verdict: 100
Time: 94ms
Memory: 11828kb

Show

[2024-11-29 21:04:40]
Submitted

answer

import math
import sys

eps = [1 , 100]

# x += y
def add(x , y):
    z = x[:]
    z[0] = x[0] * y[1] + y[0] * x[1]
    z[1] = x[1] * y[1]
    g = math.gcd(z[0],z[1])
    z[0] //= g
    z[1] //= g
    if z[1] < 0:
        z [0] *= -1
        z[1] *= -1
    return z

# x -= y
def miner(x,y):
    y[0] *= -1
    z = add(x,y)
    y[0] *= -1
    return z

# z = x * y
def mul(x,y):
    z = x[:]
    z[0] = x[0] * y[0]
    z[1] = x[1] * y[1]
    g = math.gcd(z[0],z[1])
    z[0] //= g
    z[1] //= g
    return z

# z = x/y
def div(x,y):
    y[0] , y[1] = y[1] , y[0]
    z = mul(x,y)
    y[0] , y[1] = y[1] , y[0]
    return z

# comp 1 0 -1
def comp(x , y):
    if x[0] * y[1] == y[0] * x[1]:
        return 0
    if x[0] * y[1] > y[0] * x[1]:
        return 1
    return -1

def ask(pos):
    print("?",pos[0],pos[1])
    sys.stdout.flush()
    return list(map(int,input().split(' ')))

def over(result):
    print("!",result[0],result[1])
    sys.stdout.flush()

def solve():
    n = int(input())
    points ,dic = [] ,{}

    for i in range(n):
        x , y = list(map(int,input().split(' ')))
        points.append(x)
        if x not in dic:
            dic[x] = 1
        else:
            dic[x] += 1
    
    # print(dic)
    points = list(set(points))
    # print(points)
    m = len(points)
    for i in range(m):
        points[i] = [points[i] , 1]
    points.sort()
    # print(points)
    # 左右端点的位置
    lpos ,rpos = [] , []
    llen , rlen = [] , []
    for i in range(m):
        if dic[points[i][0]] == 1:
            lpos.append(points[i])
            rpos.append(points[i])
        else:
            lpos.append(miner(points[i],eps))
            rpos.append(add(points[i],eps))

    # print("lpos:" ,lpos)
    # print("rpos:" , rpos)

    for i in range(m):
        p = points[i][0]
        if i == 0 or i == m-1:
            if dic[p] == 1:
                llen.append([0,1])
                rlen.append([0,1])
                continue
            if i == 0:
                rlen.append(ask(rpos[i]))
                llen.append([0,1])
            else:
                llen.append(ask(lpos[i]))
                rlen.append([0,1])
            continue
        # print(i,p)
        if dic[p] == 1:
            llen.append(ask(points[i]))
            rlen.append(llen[-1])
        else:
            llen.append(ask(lpos[i]))
            rlen.append(ask(rpos[i]))

    ans = [0,1]

    for i in range(1,m,1):
        lf , rf = 0 , 0
        lp , rp = points[i-1][0] , points[i][0]        
        # caulf
        if dic[lp] == 1:
            lf = rlen[i-1]
        elif i == m-1 and dic[rp] == 1:
            lf = div(mul(rlen[i-1],miner(points[i],points[i-1])) , miner(points[i],rpos[i-1]))
        else:
            lf = add(rlen[i-1] , div( mul(eps, miner(rlen[i-1] , llen[i])) , miner(lpos[i] , rpos[i-1] )))
        
        # caurf
        if dic[rp] == 1:
            rf = llen[i]
        elif i == 1 and dic[lp] == 1:
            rf = div(mul(llen[i] , miner(points[i],points[i-1])) , miner(lpos[i] , points[i-1]))     
        else:
            rf = add(llen[i] , div(mul(eps , miner(llen[i] , rlen[i-1])) , miner(lpos[i] , rpos[i-1])))

        sq = div(mul(add(lf,rf) , miner(points[i],points[i-1])),[2,1]) 
        # print(lf,rf)
        # print(sq)
        ans = add(ans , sq)
    over(ans)
    

t = int(input())
while t:
    t -= 1
    solve()

"""
3
4
0 0
1 3
1 1
3 0
1999998 1000000
3999998 2000000
3
0 0
999 1000
1000 999
1999 1000

4
0 0
1 3
1 1
3 0
2999997 1000000
1999999 2000000
"""

源文件, 语言: Python3

詳細信息

Test #1:

score: 100

Accepted

time: 10ms

memory: 10828kb

input:

output:

result:

ok correct! (2 test cases)

Test #2:

score: 0

Accepted

time: 11ms

memory: 10752kb

input:

output:

? 99 100
? 101 100
! 5 2
? 99 100
? 101 100
! 7 2
? 99 100
? 101 100
! 3 2
? 99 100
? 101 100
! 2 1
? 99 100
? 101 100
! 5 2
? 1 100
! 500000 1
? 1 100
? 99999 100
! 1000000 1
? 1 100
? 1 1
? 99999 100
! 1999999 2
? 99 100
? 101 100
? 199 100
? 201 100
? 299 100
? 301 100
? 399 100
! 4003 2

result:

ok correct! (9 test cases)

Test #3:

score: 0

Accepted

time: 24ms

memory: 10864kb

input:

output:

? 92701 100
? 937 1
? 942 1
? 95099 100
? 95101 100
? 95699 100
! 317 1
? 56201 100
? 577 1
? 582 1
? 587 1
? 60199 100
! 375 1
? 455 1
! 585 1
? 527 1
! 585 1
? 85401 100
! 600 1
? 827 1
! 300 1
? 71901 100
! 600 1
? 162 1
! 400 1
? 74201 100
? 74699 100
? 74701 100
? 75199 100
? 75201 100
? 79199 ...

result:

ok correct! (78 test cases)

Test #4:

score: 0

Accepted

time: 18ms

memory: 10880kb

input:

output:

result:

ok correct! (34 test cases)

Test #5:

score: 0

Accepted

time: 20ms

memory: 10876kb

input:

output:

? 18301 100
? 20699 100
? 20701 100
? 20799 100
? 20801 100
? 220 1
? 22099 100
? 22101 100
? 22199 100
? 22201 100
? 22299 100
? 22301 100
? 22399 100
? 22401 100
? 22499 100
? 22501 100
? 22599 100
? 22601 100
? 22699 100
? 22701 100
? 22799 100
? 22801 100
? 22899 100
? 22901 100
? 22999 100
? 23...

result:

ok correct! (47 test cases)

Test #6:

score: 0

Accepted

time: 17ms

memory: 10812kb

input:

output:

? 35001 100
? 35199 100
? 35201 100
? 35299 100
? 35301 100
? 35399 100
? 35401 100
? 35499 100
? 35501 100
? 35599 100
? 35601 100
? 35699 100
? 35701 100
? 35799 100
? 35801 100
? 35899 100
? 35901 100
? 35999 100
? 36001 100
? 36099 100
? 36101 100
? 36199 100
? 36201 100
? 36299 100
? 36301 100
...

result:

ok correct! (6 test cases)

Test #7:

score: 0

Accepted

time: 19ms

memory: 10900kb

input:

output:

? 46501 100
? 46899 100
? 46901 100
? 46999 100
? 47001 100
? 471 1
? 472 1
? 475 1
? 476 1
? 482 1
? 483 1
? 490 1
? 491 1
? 505 1
? 506 1
? 514 1
? 515 1
? 520 1
? 521 1
? 526 1
? 527 1
? 538 1
? 539 1
? 546 1
? 547 1
? 557 1
? 558 1
? 562 1
? 563 1
? 570 1
? 571 1
? 579 1
? 580 1
? 582 1
? 583 1
...

result:

ok correct! (30 test cases)

Test #8:

score: 0

Accepted

time: 24ms

memory: 10892kb

input:

12
20
69 340
411 520
513 767
826 881
199 805
622 48
945 965
677 968
388 519
825 72
122 508
448 348
982 932
838 965
448 182
716 450
8 857
346 351
792 433
224 449
117548 223
47161313 84517
7549481525 24425413
73924992225 225575873
42227227870624 157226383481
1076496201908 3834789841
6882360591313 2278...

output:

? 69 1
? 122 1
? 199 1
? 224 1
? 346 1
? 388 1
? 411 1
? 44799 100
? 44801 100
? 513 1
? 622 1
? 677 1
? 716 1
? 792 1
? 825 1
? 826 1
? 838 1
? 945 1
! 566163 2
? 100 1
? 119 1
? 123 1
? 141 1
? 152 1
? 160 1
? 178 1
? 180 1
? 183 1
? 184 1
? 186 1
? 204 1
? 213 1
? 221 1
? 242 1
? 274 1
? 279 1
? ...

result:

ok correct! (12 test cases)

Test #9:

score: 0

Accepted

time: 20ms

memory: 10852kb

input:

output:

? 7 1
? 12 1
? 33 1
? 3399 100
? 3401 100
? 38 1
? 43 1
? 97 1
? 104 1
? 108 1
? 132 1
? 134 1
? 138 1
? 14099 100
? 14101 100
? 143 1
? 147 1
? 155 1
? 193 1
? 227 1
? 235 1
? 252 1
? 253 1
? 268 1
? 291 1
? 295 1
? 315 1
? 317 1
? 332 1
? 336 1
? 34299 100
? 34301 100
? 352 1
? 355 1
? 360 1
? 398...

result:

ok correct! (47 test cases)

Test #10:

score: 0

Accepted

time: 11ms

memory: 10844kb

input:

output:

? 52401 100
? 52499 100
? 52501 100
? 52599 100
? 52601 100
? 52699 100
? 52701 100
? 52799 100
? 52801 100
? 52899 100
? 52901 100
? 52999 100
? 53001 100
? 53099 100
? 53101 100
? 53199 100
? 53201 100
? 53299 100
? 53301 100
? 53399 100
? 53401 100
? 53499 100
? 53501 100
? 53599 100
? 53601 100
...

result:

ok correct! (5 test cases)

Test #11:

score: 0

Accepted

time: 15ms

memory: 10840kb

input:

output:

? 53401 100
? 53499 100
? 53501 100
? 53599 100
? 53601 100
? 53699 100
? 53701 100
? 53799 100
? 53801 100
? 53899 100
? 53901 100
? 53999 100
? 54001 100
? 54099 100
? 54101 100
? 54199 100
? 54201 100
? 54299 100
? 54301 100
? 54399 100
? 54401 100
? 54499 100
? 54501 100
? 54599 100
? 54601 100
...

result:

ok correct! (5 test cases)

Test #12:

score: 0

Accepted

time: 19ms

memory: 10796kb

input:

output:

? 54701 100
? 54799 100
? 54801 100
? 54899 100
? 54901 100
? 54999 100
? 55001 100
? 55099 100
? 55101 100
? 55199 100
? 55201 100
? 55299 100
? 55301 100
? 55399 100
? 55401 100
? 55499 100
? 55501 100
? 55599 100
? 55601 100
? 55699 100
? 55701 100
? 55799 100
? 55801 100
? 55899 100
? 55901 100
...

result:

ok correct! (6 test cases)

Test #13:

score: 0

Accepted

time: 27ms

memory: 10836kb

input:

100
4
432 383
378 564
879 428
360 237
55425 173
20674 173
9
403 900
991 82
251 377
546 339
621 826
476 904
167 637
184 206
569 464
127483 2814
5064736823 19572978
1686763227553 5774028510
48297246268163 95848873266
57736816891 86762722
82744792 117015
554528 807
7
750 849
303 479
508 268
604 865
208...

output:

result:

ok correct! (100 test cases)

Test #14:

score: 0

Accepted

time: 27ms

memory: 11084kb

input:

10
9
243 378
841 782
148 442
136 745
35 882
560 780
385 85
443 884
953 473
28049 204
89873 204
25756 51
81469 102
19903 35
14729 199
87053 393
17
556 767
642 508
179 298
744 572
69 787
592 841
213 929
11 152
949 762
520 41
523 827
371 990
757 661
981 146
419 519
350 27
957 818
340721 4746
3276445 40...

output:

result:

ok correct! (10 test cases)

Test #15:

score: 0

Accepted

time: 22ms

memory: 11300kb

input:

output:

result:

ok correct! (1 test case)

Test #16:

score: 0

Accepted

time: 25ms

memory: 10736kb

input:

output:

result:

ok correct! (100 test cases)

Test #17:

score: 0

Accepted

time: 26ms

memory: 10884kb

input:

output:

result:

ok correct! (10 test cases)

Test #18:

score: 0

Accepted

time: 22ms

memory: 11212kb

input:

output:

result:

ok correct! (1 test case)

Test #19:

score: 0

Accepted

time: 18ms

memory: 10852kb

input:

100
22
440 908
780 215
694 883
610 182
854 925
209 611
697 442
555 903
411 296
641 308
957 488
655 836
474 34
736 125
2 734
740 68
204 1000
536 750
584 558
96 296
518 344
761 693
469436 5037
86355113 277035
107224476167 332586540
876958338859 1648151076
505945614769 921273210
9254733032 17060615
508...

output:

result:

ok correct! (100 test cases)

Test #20:

score: 0

Accepted

time: 24ms

memory: 11004kb

input:

output:

result:

ok correct! (10 test cases)

Test #21:

score: 0

Accepted

time: 32ms

memory: 11252kb

input:

output:

result:

ok correct! (1 test case)

Test #22:

score: 0

Accepted

time: 26ms

memory: 10800kb

input:

100
9
387 4
620 974
157 175
47 935
157 893
978 751
978 543
387 610
620 842
3948641 5500
2064236 2875
1742264 2875
8344891337 13770300
10430924363 13770300
4411325019 7052600
4401069143 21157800
38
678 102
793 490
747 91
930 210
409 297
585 383
922 937
573 945
770 164
963 160
741 69
63 8
678 201
656 ...

output:

? 15699 100
? 15701 100
? 38699 100
? 38701 100
? 61999 100
? 62001 100
? 97799 100
! 999589 2
? 6299 100
? 6301 100
? 29999 100
? 30001 100
? 40899 100
? 40901 100
? 44799 100
? 44801 100
? 57299 100
? 57301 100
? 58499 100
? 58501 100
? 619 1
? 63299 100
? 63301 100
? 656 1
? 67799 100
? 67801 100...

result:

ok correct! (100 test cases)

Test #23:

score: 0

Accepted

time: 31ms

memory: 11016kb

input:

output:

? 501 100
? 1499 100
? 1501 100
? 1999 100
? 2001 100
? 3299 100
? 3301 100
? 4499 100
? 4501 100
? 4599 100
? 4601 100
? 6499 100
? 6501 100
? 7199 100
? 7201 100
? 7599 100
? 7601 100
? 8599 100
? 8601 100
? 10199 100
? 10201 100
? 10699 100
? 10701 100
? 11999 100
? 12001 100
? 12399 100
? 12401 ...

result:

ok correct! (10 test cases)

Test #24:

score: 0

Accepted

time: 29ms

memory: 11076kb

input:

output:

? 201 100
? 499 100
? 501 100
? 699 100
? 701 100
? 899 100
? 901 100
? 1099 100
? 1101 100
? 1199 100
? 1201 100
? 1299 100
? 1301 100
? 2099 100
? 2101 100
? 2699 100
? 2701 100
? 2899 100
? 2901 100
? 3399 100
? 3401 100
? 3999 100
? 4001 100
? 5499 100
? 5501 100
? 5599 100
? 5601 100
? 5799 100...

result:

ok correct! (1 test case)

Test #25:

score: 0

Accepted

time: 18ms

memory: 10836kb

input:

100
4
1 1000
0 0
517 791
377 129
376871 377
92713 129
9
168 332
1 0
262 723
263 932
291 27
258 311
71 543
0 1000
70 339
262932 263
74399631 76270
82331595 106778
9302862573 14567570
7300316613 14567570
40056563 86790
1165514 4785
7
494 277
1 1000
0 0
696 595
277 739
435 88
54 196
434912 435
12525677...

output:

result:

ok correct! (100 test cases)

Test #26:

score: 0

Accepted

time: 32ms

memory: 10996kb

input:

10
9
496 52
825 592
0 0
1 1000
853 985
7 125
526 89
736 767
943 521
123987 124
8796609 8804
446131323 638716
2385697 3692
2044027 3692
1441987 8307
70740 767
17
407 499
296 912
463 41
575 862
293 242
219 602
717 283
29 11
371 775
999 1000
875 460
440 332
247 733
130 817
667 304
1000 0
56 683
457704 ...

output:

? 1 1
? 7 1
? 496 1
? 526 1
? 736 1
? 825 1
? 853 1
! 1215909 2
? 56 1
? 130 1
? 219 1
? 247 1
? 293 1
? 296 1
? 371 1
? 407 1
? 440 1
? 463 1
? 575 1
? 667 1
? 717 1
? 875 1
? 999 1
! 1163041 2
? 1 1
? 3 1
? 12 1
? 14 1
? 17 1
? 31 1
? 36 1
? 37 1
? 50 1
? 51 1
? 53 1
? 56 1
? 5999 100
? 6001 100
?...

result:

ok correct! (10 test cases)

Test #27:

score: 0

Accepted

time: 55ms

memory: 11568kb

input:

output:

result:

ok correct! (1 test case)

Test #28:

score: 0

Accepted

time: 19ms

memory: 10904kb

input:

100
8
954 724
987 177
348 574
637 423
538 43
343 0
161 1000
625 271
57136 61
2221541 2379
1209840657 1780529
5781057558027 10392947773
2500358554723 6509078017
1496781 81269
7
148 0
855 342
748 661
234 593
563 403
960 206
175 1000
403219 406
36573660 38773
8602326801 19929322
12574573 59276
9433 58
...

output:

result:

ok correct! (100 test cases)

Test #29:

score: 0

Accepted

time: 39ms

memory: 10952kb

input:

output:

result:

ok correct! (10 test cases)

Test #30:

score: 0

Accepted

time: 57ms

memory: 11544kb

input:

output:

result:

ok correct! (1 test case)

Test #31:

score: 0

Accepted

time: 27ms

memory: 10956kb

input:

100
22
780 465
411 857
2 577
854 0
736 785
518 216
641 888
209 532
655 84
780 1000
204 856
697 202
584 2
694 884
440 382
555 863
740 517
761 111
610 28
96 100
536 30
474 926
397338 8441
332712739182 3137815135
12364112649397 112961344860
4046367253037 19318027092
1010316051029 4492564440
32061030402...

output:

? 96 1
? 204 1
? 209 1
? 411 1
? 440 1
? 474 1
? 518 1
? 536 1
? 555 1
? 584 1
? 610 1
? 641 1
? 655 1
? 694 1
? 697 1
? 736 1
? 740 1
? 761 1
? 77999 100
? 78001 100
! 605895 2
? 42699 100
? 42701 100
? 697 1
? 744 1
! 310828 1
? 34 1
? 52 1
? 66 1
? 160 1
? 211 1
? 27599 100
? 27601 100
? 340 1
? ...

result:

ok correct! (100 test cases)

Test #32:

score: 0

Accepted

time: 30ms

memory: 11024kb

input:

output:

result:

ok correct! (10 test cases)

Test #33:

score: 0

Accepted

time: 53ms

memory: 11524kb

input:

output:

result:

ok correct! (1 test case)

Test #34:

score: 0

Accepted

time: 14ms

memory: 11296kb

input:

output:

result:

ok correct! (1 test case)

Test #35:

score: 0

Accepted

time: 29ms

memory: 11288kb

input:

output:

result:

ok correct! (1 test case)

Test #36:

score: 0

Accepted

time: 90ms

memory: 11736kb

input:

output:

result:

ok correct! (1 test case)

Test #37:

score: 0

Accepted

time: 80ms

memory: 11808kb

input:

output:

result:

ok correct! (1 test case)

Extra Test:

score: 0

Extra Test Passed