Category: Programming Points: 300
In each stage send the maximun size of area that can be covered by given points as a vertex of polygon in 2D. nc 18.104.22.168 12433 mirror 1 : nc 22.214.171.124 12432 mirror 2 : nc 126.96.36.199 12434 mirror 2 : nc 188.8.131.52 12429
Took me a while to figure out that the challenge was asking us to solve a Convex Hull problem.
The service provide us a list of vertices (2-D). We’ll have to find the vertices that can form a convex hull and calculate its size of area. Fortunately, there’s a python library call scipy, which can be used to find a convex hull by giving an array of vertices. After we find all the vertices, we can simply calculate the size of area by using determinant.
from pwn import * import ast import sys import numpy as np from scipy.spatial import ConvexHull from numpy import array LOG = False def my_recvuntil(s, delim): res = "" while delim not in res: c = s.recv(1) sys.stdout.write(c) res += c if LOG: print res return res def cal_area(points): pairs = zip(points, points[1:]+points[0:1]) return float(sum(x1*y2 - y1*x2 for (x1, y1), (x2, y2) in pairs)) / 2.0 HOST = "184.108.40.206" PORT = 12434 r = remote(HOST, PORT) r.recvuntil("challenge?\n") r.send("yes\n") cnt = 0 while True: log.info("Round: "+str(cnt)) cnt += 1 ps = log.progress("getting points from server...") s = my_recvuntil(r, "area? ") # parse the vertex list list_str = s[s.index("[["):s.index("What's"):].strip() real_list = ast.literal_eval(list_str) # get the convex hull point points = array(real_list) hull = ConvexHull(points) hull_points = [ real_list[c] for c in hull.vertices] final = cal_area(hull_points) log.success("answer: " + str(final)) r.send(str(final)+"\n") print r.recv(1024) r.interactive()
After solving 99 problems, we got the flag: