Problem:


輪ゴム

n 本の釘を平板上の座標 P1 (x1, y1), P2 (x2, y2), P3 (x3, y3),..., Pn (xn, yn) に１本ずつ打ち、輪ゴムの輪の中に全ての釘が入るように 1 本の輪ゴムで囲みます。このとき、輪ゴムが交差してはいけません。

釘の座標を読み込んで、上記のように釘を輪ゴムで囲んだときに輪ゴムに接していない釘の本数を出力するプログラムを作成してください。輪ゴムは充分に伸び縮みするものとします。同じ座標に 2 本以上の釘を打つことはないものとします。また、輪ゴムがかかった釘と釘の間は直線で結ばれるものとし、その直線上に 3 本以上の釘が並ぶことはないものとします。例えば、図 1 に示すような入力はありえません。図 2 に示すように輪ゴムがかかっていない釘が 1 直線上に並ぶことはありえます。

図１
図２

ただし、それぞれの座標値は -1000.0 以上1000.0 以下の実数です。また、n は 3 以上 100 以下の整数です。

Input

複数のデータセットが与えられます。各データセットは以下のような形式です与えられます。

n  
x1, y1
x2, y2
... 　　　　
...
xn, yn

n が 0 の時、入力の最後を示します。データセットの数は 50 を超えません。

Output

データセットごとに、ゴムと接していない釘の本数を出力してください。

例えば、図 3 に示す４つの釘を表す入力があった場合、図 4 のように囲まれるので、輪ゴムに接していない釘の本数は 1 本です。

図３
図４

Sample Input

4
1.0,0.0
0.0,1.0
2.0,1.0
1.0,2.0
9
-509.94,892.63
567.62,639.99
-859.32,-64.84
-445.99,383.69
667.54,430.49
551.12,828.21
-940.2,-877.2
-361.62,-970
-125.42,-178.48
0

Output for the Sample Input

0
3

Hint

以下は２つめのサンプル入力に対する図です。



Sample input:
4
1.0,0.0
0.0,1.0
2.0,1.0
1.0,2.0
9
-509.94,892.63
567.62,639.99
-859.32,-64.84
-445.99,383.69
667.54,430.49
551.12,828.21
-940.2,-877.2
-361.62,-970
-125.42,-178.48
0


Sample output:
0
3

Submission status: Wrong Answer

Solution code:
from math import atan2

def grahams_scan(a: list):
    a.sort(key=lambda x: x[1])
    x1, y1 = a[0]
    a = [((x1, y1), 0)] +\
        sorted([((x2, y2), atan2(y2-y1, x2-x1)) for x2, y2 in a[1:]], key=lambda x: x[1]) +\
        [((x1, y1), 0)]
    result = [(x1, y1)]
    for ((x2, y2),_), ((x3, y3),_) in zip(a[1:], a[2:]):
        if (x1-x2)*(y3-y2) - (y1-y2)*(x3-x2) < 0:
            result.append((x2, x3))
            x1, y1 = x2, y2
    return result

while True:
    n = int(input())
    if not n:
        break
    a = [tuple(map(float, input().split(","))) for _ in [0]*n]
    r = grahams_scan(a)
    print(n-len(r))

Submission status: Wrong Answer

Solution code:
from math import atan2

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Vector(object):
    def __init__(self, p1, p2):
        self.x = p2.x - p1.x
        self.y = p2.y - p1.y

    def cross(self, other: "Vector") -> float:
        return self.x*other.y - self.y*other.x

def grahams_scan(a: list):
    a.sort(key=lambda p: p.y)
    bottom_x, bottom_y = a[0].x, a[0].y
    _a = sorted(a[1:], key=lambda p: atan2(bottom_y-p.y, bottom_x-p.x))
    result = [a[0], _a[0]]

    for next_point in _a[1:]:
        while Vector(result[-1], result[-2]).cross(Vector(result[-1], next_point)) >= 0:
            result.pop()
        result.append(next_point)
    return result

while True:
    n = int(input())
    if not n:
        break
    a = [Point(*map(float, input().split(","))) for _ in [0]*n]
    result = grahams_scan(a)
    print(n-len(result))

Submission status: Wrong Answer

Solution code:
from math import atan2

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Vector(object):
    def __init__(self, p1, p2):
        self.x = p2.x - p1.x
        self.y = p2.y - p1.y

    def cross(self, other: "Vector") -> float:
        return self.x*other.y - self.y*other.x

def grahams_scan(a: list):
    a.sort(key=lambda p: p.y)
    bottom_x, bottom_y = a[0].x, a[0].y
    _a = sorted(a[1:], key=lambda p: atan2(bottom_y-p.y, bottom_x-p.x)) + [a[0]]
    result = [a[0], _a[0]]

    for next_point in _a[1:]:
        while Vector(result[-1], result[-2]).cross(Vector(result[-1], next_point)) >= 0:
            result.pop()
        result.append(next_point)
    return result

while True:
    n = int(input())
    if not n:
        break
    a = [Point(*map(float, input().split(","))) for _ in [0]*n]
    result = grahams_scan(a)
    print(n-len(result)-1)

Submission status: Wrong Answer

Solution code:
eps = 1e-10

def add(a, b):
    return 0 if abs(a + b) < eps * (abs(a) + abs(b)) else a + b

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(add(self.x, p.x), add(self.y, p.y))

    def __sub__(self, p):
        return Point(add(self.x, -p.x), add(self.y, -p.y))

    def __mul__(self, d):
        return Point(self.x * d, self.y * d)

    def dot(self, p):
        return add(self.x * p.x, self.y * p.y)

    def det(self, p):
        return add(self.x * p.y, -self.y * p.x)

    def __str__(self):
        return "({}, {})".format(self.x, self.y)

def convex_hull(ps):
    ps = [Point(x, y) for x, y in sorted([(p.x, p.y) for p in ps])]
    upper_hull = get_bounds(ps)
    ps.reverse()
    lower_hull = get_bounds(ps)
    del upper_hull[-1]
    del lower_hull[-1]
    upper_hull.extend(lower_hull)
    return upper_hull

def get_bounds(ps):
    qs = []
    for p in ps:
        while len(qs) > 2 and (qs[-1] - qs[-2]).det(p - qs[-1]) <= 0:
            del qs[-1]
        qs.append(p)
    return qs
    
while True:
    n = int(input())
    if n == 0: break
    points = []
    for i in range(n):
        x, y = map(float, input().split(','))
        points.append(Point(x, y))
    print(len(points) - len(convex_hull(points)))

Submission status: Wrong Answer

Solution code:
import math
def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])
while True:
    n=input()
    if n==0:
        break
    p=[0]*n
    for i in xrange(n):
        p[i]=map(float,raw_input().strip().split(","))
    P=min(p,key=lambda a:(a[1],a[0]))
    p.remove(P)
    p.sort(key=lambda x:math.atan2(P[1]-x[1],P[0]-x[0]))
    M=0
    ans=0
    for i in xrange(1,n-1):
        if not all([ccw(p[M],p[i],p[j])>=0 for j in xrange(i+1,n-1)]):
            ans+=1
        else:
            M+=1
    print ans

Submission status: Wrong Answer

Solution code:
import math
def ccw(p1,p2,p3):
#    print (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])
    return (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])
while True:
    n=input()
    if n==0:
        break
    p=[0]*n
    for i in xrange(n):
        p[i]=map(float,raw_input().strip().split(","))
    P=min(p,key=lambda a:(a[1],a[0]))
    p.remove(P)
    p.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    """
    print P,p
    for x in p:
        print x[0],x[1],math.atan2(x[1]-P[1],x[0]-P[0])
    """
    M=0
    ans=0
    for i in xrange(1,n-1):
        if not all([ccw(p[M],p[i],p[j])>=0 for j in xrange(i+1,n-1)]):
            ans+=1
        else:
            M+=1
    print ans

Submission status: Wrong Answer

Solution code:
import math
def ccw(p1,p2,p3):
    #print (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[0])>=0
    return (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[0])
while True:
    n=input()
    if n==0:
        print n
        break
    p=[0]*n
    for i in xrange(n):
        p[i]=map(float,raw_input().strip().split(","))
    P=min(p,key=lambda a:(a[1],a[0]))
    p.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    M=0
    ans=0
    i=1
    #print M,p
    while M<len(p)-1:
        if all([ccw(p[M-1],p[M],p[i])>=0 for i in xrange(M+1,len(p))]):
            M+=1
        else:
            ans+=1
            p.remove(p[M])
        #print M,p
    print ans
#    print len(p)
#    print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))

Submission status: Wrong Answer

Solution code:
import sys
def side(p1,p2):
  global D
  y1,x1=p1
  y2,x2=p2
  dy=y2-y1
  dx=x2-x1
  for p3 in D[::-1]:
    if p1==p3 or p2==p3:pass
    elif (x2-x1)*dy-dx*(y2-y1)<0:return 0
  else:return 1

while 1:
  n=input()
  if n==0:break
  D=sorted([list(input()) for i in range(n)])
  p=p1=D[0]
  D1=D[:]
  while True:
    for p2 in D1:
      if p1!=p2 and side(p1,p2):break
    p1=p2
    D1.remove(p2)
    if p2==p:break
  print len(D1)

Submission status: Wrong Answer

Solution code:
def f(x,y,x1,y1,x2,y2):
    if x1 <= x2:
        return (x2-x1)*y-(y2-y1)*x+x1*y2-x2*y1
    else:
        return -((x2-x1)*y-(y2-y1)*x+x1*y2-x2*y1)

def DC(a):
    if len(a) > 3:
        # Divide
        la = a[:len(a)/2]
        ra = a[len(a)/2:]
        # Conquer
        la,ra = DC(la),DC(ra)
        while len(ra) > 1 and f(ra[1][0],ra[1][1],la[-1][0],la[-1][1],ra[0][0],ra[0][1]) > 0:
            ra.pop(0)
        while len(la) > 1 and f(la[-2][0],la[-2][1],ra[0][0],ra[0][1],la[-1][0],la[-1][1]) > 0:
            la.pop(-1)
        return la+ra
    else:
        return a

while True:
    n = int(raw_input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(map(float, raw_input().split(",")))
    p = sorted(p, key = lambda x: x[0])
    print n - len(DC(p))

Submission status: Wrong Answer

Solution code:
def f(x,y,x1,y1,x2,y2):
    if x1 <= x2:
        return (x2-x1)*y-(y2-y1)*x+x1*y2-x2*y1
    else:
        return -((x2-x1)*y-(y2-y1)*x+x1*y2-x2*y1)

def DC(a):
    if len(a) > 3:
        # Divide
        la = a[:len(a)/2]
        ra = a[len(a)/2:]
        # Conquer
        la,ra = DC(la),DC(ra)
        while len(ra) > 1 and f(ra[1][0],ra[1][1],la[-1][0],la[-1][1],ra[0][0],ra[0][1]) > 0:
            ra.pop(0)
        while len(la) > 1 and f(la[-2][0],la[-2][1],ra[0][0],ra[0][1],la[-1][0],la[-1][1]) > 0:
            la.pop()
        return la+ra
    else:
        return a

while True:
    n = int(raw_input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(map(float, raw_input().split(",")))
    p = sorted(p, key = lambda x: x[0])
    print n - len(DC(p))

Submission status: Wrong Answer

Solution code:
def f(x,y,x1,y1,x2,y2):
    if x1 <= x2:
        return (x2-x1)*y-(y2-y1)*x+x1*y2-x2*y1
    else:
        return -((x2-x1)*y-(y2-y1)*x+x1*y2-x2*y1)

def DC(a):
    if len(a) > 3:
        # Divide
        la = a[:len(a)/2]
        ra = a[len(a)/2:]
        # Conquer
        la,ra = DC(la),DC(ra)
        while len(ra) > 1 and f(ra[1][0],ra[1][1],la[-1][0],la[-1][1],ra[0][0],ra[0][1]) > 0.0:
            ra.pop(0)
        while len(la) > 1 and f(la[-2][0],la[-2][1],ra[0][0],ra[0][1],la[-1][0],la[-1][1]) > 0.0:
            la.pop()
        return la+ra
    else:
        return a

while True:
    n = int(raw_input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(map(float, raw_input().split(",")))
    p = sorted(p, key = lambda x: x[0])
    print n - len(DC(p))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math


def deg(v1,v2):
    normv1 = math.sqrt(v1[0]**2+v1[1]**2)
    normv2 = math.sqrt(v2[0]**2+v2[1]**2)
    if normv1 == 0 or normv2 == 0:
        print "ERROR"; exit()
    return (v1[0]*v2[0]+v1[1]*v2[1])/(normv1*normv2)

def calc_hull(d):
    hull = []
    point_first = d[0]
    hull.append(point_first)
    v = [ 1, 0 ]
    oldpoint=point_first
    while True:
        minipoint = 0;
        minv = [ 0,0 ]
        maxcos = -1
        for p in d:
            if p == oldpoint: continue
            o = [ p[i]-oldpoint[i] for i in xrange(2) ]
            cos = deg(o,v)
            if cos > maxcos:
                maxcos = cos
                minv = o
                minpoint = p
        if minpoint == point_first: break
        v = minv
        oldpoint = minpoint
        hull.append(minpoint)
    return hull

while True:
    n = int(raw_input())
    if n == 0: break
    d = []
    for t in xrange(n):
        d.append(map(float,raw_input().split(",")))
    h = calc_hull(sorted(d,key=lambda x:-x[1]))
    print len(d) - len(calc_hull(d))

Submission status: Accepted

Solution code:
from math import atan2

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Vector(object):
    def __init__(self, p1, p2):
        self.x = p2.x - p1.x
        self.y = p2.y - p1.y

    def cross(self, other: "Vector") -> float:
        return self.x*other.y - self.y*other.x

def grahams_scan(a: list):
    a.sort(key=lambda p: p.y)
    bottom_x, bottom_y = a[0].x, a[0].y
    _a = sorted(a[1:], key=lambda p: atan2(bottom_y-p.y, bottom_x-p.x)) + [a[0]]
    result = [a[0], _a[0]]

    for next_point in _a[1:]:
        while Vector(result[-1], result[-2]).cross(Vector(result[-1], next_point)) >= 0:
            result.pop()
        result.append(next_point)
    return result

while True:
    n = int(input())
    if not n:
        break
    a = [Point(*map(float, input().split(","))) for _ in [0]*n]
    result = grahams_scan(a)
    print(n-len(result)+1)

Submission status: Accepted

Solution code:
import sys
import math


def deg(v1,v2):
    normv1 = math.sqrt(v1[0]**2+v1[1]**2)
    normv2 = math.sqrt(v2[0]**2+v2[1]**2)
    if normv1 == 0 or normv2 == 0:
        print "ERROR"; exit()
    return (v1[0]*v2[0]+v1[1]*v2[1])/(normv1*normv2)

def calc_hull_right(d):
    hull_right = [d[0]]
    first = d[0]
    p = d[0]
    while True:
        maxcos = -1.0
        for i in xrange(1,len(d)):
            if d[i][1] < p[1]  or d[i] == p: continue
            c = deg([d[i][0]-p[0],d[i][1]-p[1]],[1,0])
            if c >= maxcos:
                maxcos = c
                q = d[i]
        p = q
        hull_right.append(q)
        if q == d[-1]: break
    return hull_right


def calc_hull_left(d):
    hull_left = [d[0]]
    first = d[0]
    p = d[0]
    while True:
        maxcos = 1.0
        for i in xrange(1,len(d)):
            if d[i][1] < p[1]  or d[i] == p: continue
            c = deg([d[i][0]-p[0],d[i][1]-p[1]],[1,0])
            if c <= maxcos:
                maxcos = c
                q = d[i]
        p = q
        hull_left.append(q)
        if q == d[-1]: break
    return hull_left

while True:
    n = int(raw_input())
    if n == 0: break
    d = []
    for t in xrange(n):
        d.append(map(float,raw_input().split(",")))
    d.sort(key = lambda x:x[1])
    #print calc_hull_left(d) + calc_hull_right(d)
    print  - len( calc_hull_left(d) + calc_hull_right(d) ) + 2 + len(d)

Submission status: Accepted

Solution code:
import sys

def calc_hull(d,direction):
    maxcos0 = {"r":-1.0,"l":1.0}
    hull = [d[0]]
    p = d[0]
    while True:
        maxcos = maxcos0[direction]
        for i in xrange(1,len(d)):
            if d[i][1] < p[1]  or d[i] == p: continue
            v = [ d[i][0]-p[0] , d[i][1]-p[1] ]
            c = v[0]/(v[0]**2+v[1]**2)**0.5
            if c >= maxcos and direction == "r":
                maxcos = c
                q = d[i]
            if c <= maxcos and direction == "l":
                maxcos = c
                q = d[i]
        p = q
        hull.append(q)
        if q == d[-1]: break
    return hull

while True:
    n = int(raw_input())
    if n == 0: break
    d = []
    for t in xrange(n):
        d.append(map(float,raw_input().split(",")))
    d.sort(key = lambda x:x[1])
    print len(d) - ( len( calc_hull(d,"r") + calc_hull(d,"l") ) - 2)

Submission status: Accepted

Solution code:
def area(x1,y1,x2,y2,x3,y3):
    return ((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/2.0
def totu(S,d):
    if len(S)<=3:
        if len(S)==3:
            if d=="r":
                if area(S[0][0],S[0][1],S[1][0],S[1][1],S[2][0],S[2][1])>0:
                    S[1],S[2]=S[2],S[1]
                    
            else:
                if area(S[0][0],S[0][1],S[1][0],S[1][1],S[2][0],S[2][1])>0:
                    S=[S[2],S[0],S[1]]
                else:
                    S=[S[2],S[1],S[0]]
        if len(S)==2:
            if d=="l":
                S[0],S[1]=S[1],S[0]
        return S

    else:
        S1=totu(S[:len(S)/2],"l")
        S2=totu(S[len(S)/2:],"r")
        ue_old_ri=0
        ue_old_li=0
        ue_new_ri=0
        ue_new_li=0

        while True:
            for i in [i for i in range(len(S2)) if i>=ue_old_ri]:
                if  area(S1[ue_old_li][0],S1[ue_old_li][1],S2[i][0],S2[i][1],S2[(i+1)%len(S2)][0],
                         S2[(i+1)%len(S2)][1])<=0:
                    ue_new_ri=i
                    break
            for j in [j for j in range(len(S1)) if j>=ue_old_li]:
                if area(S2[ue_new_ri][0],S2[ue_new_ri][1],S1[j][0],S1[j][1],S1[(j+1)%len(S1)][0],
                        S1[(j+1)%len(S1)][1])>=0:
                    ue_new_li=j
                    break
            if ue_old_ri==ue_new_ri and ue_old_li==ue_new_li:
                break
            ue_old_ri,ue_old_li=ue_new_ri,ue_new_li
        si_old_ri=0
        si_old_li=0
        si_new_ri=0
        si_new_li=0
        while True:
            for i in [-i for i in range(len(S2)) if (-1)*i<=si_old_ri]:
                if  area(S1[si_old_li%len(S1)][0],S1[si_old_li%len(S1)][1],S2[i%len(S2)][0],S2[i%len(S2)][1],S2[(i-1)%len(S2)][0],
                         S2[(i-1)%len(S2)][1])>=0:
                    si_new_ri=i
                    break
            for j in [-j for j in range(len(S1)) if (-1)*j<=si_old_li]:
                if area(S2[si_new_ri%len(S2)][0],S2[si_new_ri%len(S2)][1],S1[j%len(S1)][0],S1[j%len(S1)][1],S1[(j-1)%len(S1)][0],
                        S1[(j-1)%len(S1)][1])<=0:
                    si_new_li=j
                    break
            if si_old_ri==si_new_ri and si_old_li==si_new_li:
                break
            si_old_ri,si_old_li=si_new_ri,si_new_li
        if d=="r":
            Sx=[]
            i=0
            while True:
                Sx.append(S2[(i+ue_old_ri)%len(S2)])
                if (i+ue_old_ri)%len(S2)==si_old_ri%len(S2):
                    break
                i+=1

            Sy=[]
            j=0
            while True:
                Sy.append(S1[(si_old_li-j)%len(S1)])
                if (si_old_li-j)%len(S1)==ue_old_li%len(S1):
                    break
                j+=1

            S=Sx+Sy
            m=S.index(min(S))
            S_d=[]
            for i in range(len(S)):
                S_d.append(S[(m+i)%len(S)])
            return S_d
        else:
            Sx=[]
            i=0
            while True:
                Sx.append(S1[(i+ue_old_li)%len(S1)])
                if (i+ue_old_li)%len(S1)==si_old_li%len(S1):
                    break
                i+=1

            Sy=[]
            j=0
            while True:
                Sy.append(S2[(si_old_ri-j)%len(S2)])
                if (si_old_ri-j)%len(S2)==ue_old_ri%len(S2):
                    break
                j+=1

            S=Sx+Sy
            m=S.index(max(S))
            S_d=[]
            for i in range(len(S)):
                S_d.append(S[(m+i)%len(S)])
            return S_d

while True:
    L=[]
    n=input()
    prin=n
    if n==0:
        break
    while n!=0:
        L.append(map(float,raw_input().split(",")))
        n-=1
    L.sort()
    L=totu(L,"l")
    print prin-len(L)

Submission status: Accepted

Solution code:
eps = 1e-10

def add(a, b):
    return 0 if abs(a + b) < eps * (abs(a) + abs(b)) else a + b

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(add(self.x, p.x), add(self.y, p.y))

    def __sub__(self, p):
        return Point(add(self.x, -p.x), add(self.y, -p.y))

    def __mul__(self, d):
        return Point(self.x * d, self.y * d)

    def dot(self, p):
        return add(self.x * p.x, self.y * p.y)

    def det(self, p):
        return add(self.x * p.y, -self.y * p.x)

    def __str__(self):
        return "({}, {})".format(self.x, self.y)




def convex_hull(ps):
    ps = [Point(x, y) for x, y in sorted([(p.x, p.y) for p in ps])]
    upper_hull = get_bounds(ps)
    ps.reverse()
    lower_hull = get_bounds(ps)
    del upper_hull[-1]
    del lower_hull[-1]
    upper_hull.extend(lower_hull)
    return upper_hull

def get_bounds(ps):
    qs = [ps[0], ps[1]]
    for p in ps[2:]:
        while len(qs) > 1 and (qs[-1] - qs[-2]).det(p - qs[-1]) <= 0:
            del qs[-1]
        qs.append(p)
    return qs
    
while True:
    n = int(input())
    if n == 0: break
    points = []
    for i in range(n):
        x, y = map(float, input().split(','))
        points.append(Point(x, y))
    print(len(points) - len(convex_hull(points)))

Submission status: Accepted

Solution code:
eps = 1e-10

def add(a, b):
    return 0 if abs(a + b) < eps * (abs(a) + abs(b)) else a + b

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(add(self.x, p.x), add(self.y, p.y))

    def __sub__(self, p):
        return Point(add(self.x, -p.x), add(self.y, -p.y))

    def __mul__(self, d):
        return Point(self.x * d, self.y * d)

    def dot(self, p):
        return add(self.x * p.x, self.y * p.y)

    def det(self, p):
        return add(self.x * p.y, -self.y * p.x)

    def __str__(self):
        return "({}, {})".format(self.x, self.y)

def convex_hull(ps):
    ps = [Point(x, y) for x, y in sorted([(p.x, p.y) for p in ps])]
    lower_hull = get_bounds(ps)
    ps.reverse()
    upper_hull = get_bounds(ps)
    del upper_hull[-1]
    del lower_hull[-1]
    lower_hull.extend(upper_hull)
    return lower_hull

def get_bounds(ps):
    qs = [ps[0], ps[1]]
    for p in ps[2:]:
        while len(qs) > 1 and (qs[-1] - qs[-2]).det(p - qs[-1]) <= 0:
            del qs[-1]
        qs.append(p)
    return qs
    
while True:
    n = int(input())
    if n == 0: break
    points = []
    for i in range(n):
        x, y = map(float, input().split(','))
        points.append(Point(x, y))
    print(len(points) - len(convex_hull(points)))

Submission status: Accepted

Solution code:
while 1:
        n = input()
        if n == 0:
                break
        x = []
        y = []
        for i in range(n):
                a,b = map(float,raw_input().split(','))
                x.append(a)
                y.append(b)
        ys = y.index(min(y))
        s = ys
        vx = 1.0
        vy = 0.0
        ans = n
        while 1:
                cx = -1.0
                t = -1
                for i in range(n):
                        if i != s:
                                tx = x[i] - x[s]
                                ty = y[i] - y[s]
                                d = (tx**2 + ty**2) ** 0.5
                                c = (vx*tx + vy*ty) / d
                                if cx < c:
                                        cx = c
                                        t = i
                ans -= 1
                if t == ys:
                        break
                vx = x[t] - x[s]
                vy = y[t] - y[s]
                s = t
        print ans

Submission status: Accepted

Solution code:
def a(v1,v2):
    if v1[0]!=v2[0]:
        return (v2[1]-v1[1])/(v2[0]-v1[0])
    else:
        return (v2[1]-v1[1])*(10**10)

def dlt(p,v,sign):
    while len(p)>2:
        if sign*(a(v[p[-3]],v[p[-2]])-a(v[p[-2]],v[p[-1]]))<0:
            del p[-2]
        else:
            break
    return p

def convex(v,n):
    d,u=[],[]
    for i in range(n):
        d=dlt(d+[i],v,1)
        u=dlt(u+[i],v,-1)
    return n-len(set(d+u))

while 1:
    n=int(raw_input())
    if n==0:
        break
    v=[map(float,raw_input().split(',')) for i in range(n)]
    v=sorted(sorted(v,key=lambda x:x[1]))
    print convex(v,n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# ????????????????????°???????????°????????????????????\??????????????¢?????´???????????¨??????????§???????
# ?????????http://www.prefield.com/algorithm/geometry/convex_hull.html

import enum


EPS = 1e-10


class PointsRelation(enum.Enum):
    counter_clockwise = 1
    clockwise = 2
    online_back = 3
    on_segment = 4
    online_front = 5


def inner_product(v1, v2):
    return v1.real * v2.real + v1.imag * v2.imag


def outer_product(v1, v2):
    return v1.real * v2.imag - v1.imag * v2.real


def project(a, b):
    return a * inner_product(a, b) / (abs(a) ** 2)


def points_relation(p0, p1, p2):
    v1 = p1 - p0
    v2 = p2 - p0
    op = outer_product(v1, v2)
    if op > EPS:
        return PointsRelation.counter_clockwise
    elif op < -EPS:
        return PointsRelation.clockwise
    elif inner_product(v1, v2) < -EPS:
        return PointsRelation.online_back
    elif abs(v1) < abs(v2):
        return PointsRelation.online_front
    else:
        return PointsRelation.on_segment


def in_place_convex_hull_andrew(ps):
    def judge(p0, p1, p2):
        b = points_relation(p0, p1, p2) != PointsRelation.counter_clockwise
        b &= points_relation(p0, p1, p2) != PointsRelation.online_front
        return b
    if len(ps) < 3:
        return ps
    ps.sort(key=lambda p: p.imag)
    n = len(ps)
    k = 0
    ch = [None for _ in range(2 * n)]
    for i in range(n):
        while k >= 2 and judge(ch[k - 2], ch[k - 1], ps[i]):
            k -= 1
        ch[k] = ps[i]
        k += 1
    t = k + 1
    for i in range(n - 1)[::-1]:
        while k >= t and judge(ch[k - 2], ch[k - 1], ps[i]):
            k -= 1
        ch[k] = ps[i]
        k += 1
    ch = ch[:k - 1]
    return ch


def main():
    while True:
        n = int(input())
        if n == 0:
            return
        ps = [complex(*map(float, input().split(","))) for _ in range(n)]
        ch = in_place_convex_hull_andrew(ps)
        print(n - len(ch))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def op(x,y):
    """
    Outer product
    """
    return(complex.conjugate(x)*y).imag

def isrm(q,i,x):   
    """
    is i right most to q's from view of x?
    """
    for j in q:
        if op(i-x, j-x) < 0:
            return(False)
    return(True)

def rightmost(p,x):
    """
    Find a point in p which is rightmost from x(other than x)
    """
    for i in [i for i in p if i!=x]:
        q = p.copy()
        q.remove(i)
        if isrm(q,i,x):
            return(i)
    raise ValueError('Do not come here')

def solve(p,pf,orig):
    nx = rightmost(p,orig)
    ni = p.index(nx)
    if pf[ni]:   # second visit
        return(pf)
    pf[ni] = True
    return(solve(p,pf,nx))

while True:
    p = []
    n = int(input().strip())
    if n==0:
        break
    for i in range(n):
        x,y = list(map(float, input().strip().split(',')))
        p.append(x+y*1j)
    print(solve(p,[False for _ in range(n)],2000.0 + 0.0*1j).count(False))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

for s in sys.stdin:
    N = int(s)
    if N == 0:
        break

    X = []
    Y = []
    visited = [False] * N

    for i in range(N):
        x, y = map(float, input().split(','))
        X.append(x)
        Y.append(y)

    def paint(start_i, is_right, is_up):
        x_start = X[start_i]
        y_start = Y[start_i]
        visited[start_i] = True

        if is_right:
            dir_sign = 1 # search right only
        else:
            dir_sign = -1 # search left only

        if (is_up and is_right) or (not is_up and not is_right) :
            min_max_sign = 1 # search min
        else:
            min_max_sign = -1 # search max

        tangent_min_i = None
        tangent_min = None
        for i, x in enumerate(X):
            if dir_sign * (x - x_start) > 0:
                y = Y[i]
                tangent = (y - y_start) / (x - x_start)
                if tangent_min is None:
                    tangent_min = tangent
                    tangent_min_i = i
                else:
                    if min_max_sign * (tangent_min - tangent) > 0:
                        tangent_min = tangent
                        tangent_min_i = i
        if tangent_min_i is not None:
            paint(tangent_min_i, is_right, is_up)


    start_index = Y.index(min(Y))
    visited[start_index] = True
    paint(start_index, is_right=True, is_up=True)
    paint(start_index, is_right=False, is_up=True)

    start_index = Y.index(max(Y))
    visited[start_index] = True
    paint(start_index, is_right=True, is_up=False)
    paint(start_index, is_right=False, is_up=False)

    visit_num = 0
    for is_visit in visited:
        if is_visit:
            visit_num += 1
    print(len(X) - visit_num)

Submission status: Accepted

Solution code:
# Aizu Problem 0068: Enclose Pins with a Rubber Band
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def is_to_the_left(p1, p2, p3):
    # determine whether point p3 is to the left from the line from p1 to p2
    position = (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])
    return position < 0

def jarvis(points):
    # determine convex hull by Jarvis' algorithm:
    max_y = max([p[1] for p in points])
    pointOnHull = [p for p in points if p[1] == max_y][0]
    convex_hull = [pointOnHull]
    while len(convex_hull) == 1 or convex_hull[-1] != convex_hull[0]:
        p = convex_hull[-1]
        endpoint = points[0]
        for j in range(len(points)):
            if endpoint == pointOnHull or is_to_the_left(p, endpoint, points[j]):
                endpoint = points[j]
        pointOnHull = endpoint
        convex_hull.append(pointOnHull)
    return convex_hull[::-1]

while True:
    N = int(input())
    if N == 0:
        break
    points = [[float(_) for _ in input().split(',')] for __ in range(N)]
    print(N - (len(jarvis(points)) - 1))

Submission status: Accepted

Solution code:
import math
def vec(a, b):
    return [b[0] - a[0], b[1] - a[1]]

def norm(a):
    return math.sqrt(a[0]**2 + a[1]**2)

def cross(a, b):
    return a[0]*b[1] - b[0]*a[1]

def gift_wrap(p_a, p_h, a):
    while True:
        p_h.append(a)
        b = p_a[0]
        for i in range(len(p_a)):
            c = p_a[i]
            if b == a:
                b = c
            else:
                ab = vec(a, b)
                ac = vec(a, c)
                v = cross(ab, ac)
                if v > 0 or (v == 0 and norm(ac) > norm(ab)):
                    b = c
        a = b
        if a == p_h[0]:
            break

while True:
    n = int(input())
    if n == 0:
        break
    p_all = []
    p_hull = []
    for i in range(n):
        p_all.append(list(map(float, input().split(","))))
    p_all = sorted(p_all)
    gift_wrap(p_all, p_hull, p_all[0])
    print(len(p_all) - len(p_hull))

Submission status: Accepted

Solution code:
# AOJ 0068 Enclose Pins with a Rubber Band
# Python3 2018.6.22 bal4u

def cross(a, b):
	return a.real*b.imag - a.imag*b.real
	
# 凸包　入力: 座標リスト　リターン:凸包を構成する座標リスト
def convex_hull(p):
	pp = sorted(p, key=lambda x:(x.imag,x.real))  # y座標を優先して昇順、同じならx座標で昇順
	n = len(pp)
	ans, j = [0]*(n+1), 0
	for i in range(n):
		while j > 1 and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) <= 0: j -= 1
		ans[j] = pp[i]
		j += 1
	k = j
	for i in range(n-2, -1, -1):
		while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) <= 0: j -= 1
		ans[j] = pp[i]
		j += 1
	return ans[0:j-1]
	
while 1:
	n = int(input())
	if n == 0: break
	p = []
	for i in range(n):
		x, y = list(map(float, input().split(',')))
		p.append(complex(x, y))
	print(n - len(convex_hull(p)))

Submission status: Accepted

Solution code:
# AOJ 0068 Enclose Pins with a Rubber Band
# Python3 2018.6.22 bal4u

def cross(a, b):
	return a.real*b.imag - a.imag*b.real
	
# 凸包　入力: 座標リスト　リターン:凸包を構成する座標リスト
def convex_hull(p):
	pp = sorted(p, key=lambda x:(x.imag,x.real))  # y座標を優先して昇順、同じならx座標で昇順
	n = len(pp)
	ans, j = [0]*(n+1), 0
	for i in range(n):
		while j > 1 and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	k = j
	for i in range(n-2, -1, -1):
		while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: j -= 1
		ans[j] = pp[i]
		j += 1
	return ans[0:j-1]
	
while 1:
	n = int(input())
	if n == 0: break
	p = []
	for i in range(n):
		x, y = list(map(float, input().split(',')))
		p.append(complex(x, y))
	print(n - len(convex_hull(p)))