QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742015#3139. Largest Quadrilateralvwxyz#WA 26ms11424kbPython32.3kb2024-11-13 15:38:322024-11-13 15:38:36

Judging History

This is the latest submission verdict.

  • [2024-11-13 15:38:36]
  • Judged
  • Verdict: WA
  • Time: 26ms
  • Memory: 11424kb
  • [2024-11-13 15:38:32]
  • Submitted

answer

def Cross_Product(P0,P1,P2):
    x0,y0=P0
    x1,y1=P1
    x2,y2=P2
    return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)
def Convex_Hull(points,upper_lower=False):
    sorted_points=sorted(points,reverse=True)
    upper_convex_hull=[]
    lower_convex_hull=[]
    for x,y in sorted_points:
        if not upper_convex_hull or upper_convex_hull[-1]!=(x,y):
            while len(upper_convex_hull)>=2 and Cross_Product(upper_convex_hull[-2],(x,y),upper_convex_hull[-1])>0:
                upper_convex_hull.pop()
            upper_convex_hull.append((x,y))
        if not lower_convex_hull or lower_convex_hull[-1]!=(x,y):
            while len(lower_convex_hull)>=2 and Cross_Product(lower_convex_hull[-2],lower_convex_hull[-1],(x,y))>0:
                lower_convex_hull.pop()
            lower_convex_hull.append((x,y))
    if upper_lower:
        return upper_convex_hull,lower_convex_hull
    else:
        retu=[]
        for x,y in upper_convex_hull+lower_convex_hull[::-1]:
            if not retu or retu[-1]!=(x,y) and retu[0]!=(x,y):
                retu.append((x,y))
        return retu


T=int(input())
for t in range(T):
    N=int(input())
    X,Y=[],[]
    XY=[]
    for i in range(N):
        x,y=map(int,input().split())
        X.append(x)
        Y.append(y)
        XY.append((x,y))
    P=Convex_Hull(XY)
    le=len(P)
    if le>=4:
        def S(i,j,k):
            return abs(Cross_Product(P[i%le],P[j%le],P[k%le]))
        ans=0
        for a in range(le):
            b,d=a,a
            for c in range(a+2,a+le-1):
                while b<=a:
                    b+=1
                while d<=c:
                    d+=1
                while b+1<c and S(a,b,c)<=S(a,b+1,c):
                    b+=1
                while d+1<a+le and S(a,c,d)<=S(a,c,d+1):
                    d+=1
                ans=max(ans,S(a,b,c)+S(a,c,d))
    elif le==3:
        def S(i,j,k):
            return abs(Cross_Product(XY[i],XY[j],XY[k]))
        ans=0
        a,b,c=[XY.index(p) for p in P]
        for i in range(N):
            if i in (a,b,c):
                continue
            ans=max(ans,S(a,b,c)-S(a,b,i))
            ans=max(ans,S(a,b,c)-S(b,c,i))
            ans=max(ans,S(a,b,c)-S(a,c,i))
            
    else:
        ans=0
    if ans%2:
        ans/=2
    else:
        ans//=2
    print(ans)


详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 10576kb

input:

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

output:

3
6
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 15ms
memory: 10748kb

input:

1
4
0 0
1 0
0 1
3 2

output:

2.5

result:

ok single line: '2.5'

Test #3:

score: 0
Accepted
time: 7ms
memory: 10616kb

input:

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

output:

0
3
6

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 14ms
memory: 10580kb

input:

3
4
0 0
1 1
2 2
1 1
5
0 0
3 3
1 1
4 4
2 2
6
0 0
0 4
4 0
0 0
1 1
1 2

output:

0
0
8

result:

ok 3 lines

Test #5:

score: -100
Wrong Answer
time: 26ms
memory: 11424kb

input:

3
6
0 0
8 8
7 9
6 9
5 8
0 99
29
999891293 708205
369022896 771
993004062 999827531
929592437 29458
994968624 999539287
569046020 1943
2200 986643253
11189 5792636
712825 999917190
2482686 272282
43058 665660
10373878 31825
508452623 112
3304 269412577
43817590 3789
999996618 957802194
999902626 9749...

output:

388
9.967750187312918e+17
9.650057065677044e+17

result:

wrong answer 2nd lines differ - expected: '996775018731291724.5', found: '9.967750187312918e+17'