# ASIS CTF 2015 Quals – grids

**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 217.218.48.84 12433 mirror 1 : nc 217.218.48.84 12432 mirror 2 : nc 217.218.48.84 12434 mirror 2 : nc 217.218.48.84 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 = "217.218.48.84"
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: `ASIS{f3a8369f4194c5e44c03e5fcefb8ddf6}`

## Comments