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: Accepted

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:
        #print 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.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    #print len(p)
    #print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))
    M=0
    ans=0
    for i in xrange(1,n):
        while ccw(p[M-1],p[M],p[i])<=0:
            if M>0:
                M-=1
                ans+=1
            elif i==n:
                break
            else:
                i+=1
                
        M+=1
        p[M],p[i]=p[i],p[M]
    print ans
    #print len(p)
    #print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))

Submission status: Accepted

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:
        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]))
    #print n
    #print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))
    M=0
    i=1
    c_p=p[:]
    #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:
            p.remove(p[M])
        #print M,p
    print len(c_p)-len(p)
    #print len(p)
    #print "\n".join(map(lambda x:"{},{}".format(x[0],x[1]),p))

Submission status: Accepted

Solution code:
import math
def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[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.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    M=0
    ans=0
    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 ans

Submission status: Accepted

Solution code:
import math
def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[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.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    M=0
    ans=0
    for i in xrange(1,n-1):
        if all([ccw(p[M],p[i],p[j])>=0 for j in xrange(i+1,n)]):
            M=i
        else:
            ans+=1
    print ans

Submission status: Accepted

Solution code:
import math
def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[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.sort(key=lambda x:math.atan2(x[1]-P[1],x[0]-P[0]))
    M,ans=0,0
    for i in xrange(1,n-1):
        if all([ccw(p[M],p[i],p[j])>=0 for j in xrange(i+1,n)]):
            M=i
        else:
            ans+=1
    print ans

Submission status: Accepted

Solution code:
import math
def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p2[1])-(p2[1]-p1[1])*(p3[0]-p2[0])
while True:
    n=input()
    if n==0:
        break
    p=[0]*n
    for i in xrange(n):
        p[i]=map(float,raw_input().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,ans=0,0
    for i in xrange(1,n-1):
        if all([ccw(p[M],p[i],p[j])>=0 for j in xrange(i+1,n)]):
            M=i
        else:
            ans+=1
    print ans

Submission status: Accepted

Solution code:
def func(u,v):
    f=lambda x,y:(v[0]-u[0])*(y-u[1])-(v[1]-u[1])*(x-u[0])
    return f

while True:
    n=input()
    if n==0:break
    L=[map(float,raw_input().split(",")) for i in range(n)]
    L.sort()
    S=[]
    init=L[0]
    for i in range(n):
        if L[i]!=init:
            f=func(init,L[i])
            for j in range(i+1,n):
                if f(L[j][0],L[j][1])>0:
                    break
            else:
                S.append(L[i])
                init=L[i]
    init=L[0]
    for i in range(n):
        if L[i]!=init:
            f=func(init,L[i])
            for j in range(i+1,n):
                if f(L[j][0],L[j][1])<0:
                    break
            else:
                S.append(L[i])
                init=L[i]
    print n-len(set(map(tuple,S)))-1

Submission status: Accepted

Solution code:

import sys
import math


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


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

    def length(self):
        return math.sqrt(self.vx ** 2.0 + self.vy ** 2.0)

    def degree(self, other):
        theta = math.acos((self.vx * other.vx + self.vy * other.vy)/(self.length() * other.length()))
        return theta

    def show(self):
        return "Vector(%f, %f)" % (self.vx, self.vy)


def solv(points):
    p0 = points[0]
    for p in points[1:]:
        if p.y < p0.y:
            p0 = p
    v1 = Vector(Point(0.0, 0.0), Point(1.0, 0.0))
    p1 = p0
    t = [p1]
    while True:
        min_deg = math.pi
        next_p = None
        next_v = None
        points2 = list(points)
        points2.remove(p1)
        for p2 in points2:
            v2 = Vector(p1, p2)
            deg = v1.degree(v2)
            if deg < min_deg:
                min_deg = deg
                next_p = p2
                next_v = v2
        if next_p == p0:
            break
        p1 = next_p
        t.append(p1)
        v1 = next_v
    return len(points) - len(t)



while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    points = []
    for i in range(n):
        x, y = map(float, sys.stdin.readline().split(','))
        points.append(Point(x, y))
    print solv(points)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from math import copysign


def gradient(p):
    def fn(t):
        dx = p[0] - t[0]
        dy = p[1] - t[1]
        if dx:
            return dy / dx
        return copysign(float('inf'), -dy)
    return fn


def solve(n):
    L = []
    for i in range(n):
        L.append(tuple(float(s) for s in stdin.readline().split(',')))
    L.sort()

    p = p0 = L.pop(0)
    while True:
        p = max((t for t in L if t[0] >= p[0]), key=gradient(p))
        if p == L[-1]:
            break
        L.remove(p)

    p = p0
    while True:
        p = min((t for t in L if t[0] >= p[0]), key=gradient(p))
        if p == L[-1]:
            break
        L.remove(p)

    return len(L) - 1

while True:
    n = int(stdin.readline())
    if not n:
        break
    print(solve(n))

Submission status: Accepted

Solution code:
import sys
def side(p1, p2, p3):
  y1,x1=p1
  y2,x2=p2
  y3,x3=p3
  return (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>0
while 1:
  n=input()
  if n==0:break
  D=[input() for i in range(n)]
  for p1 in D:
    c=0
    for p2 in D:
      if p1==p2:continue
      f=[0,0]
      for p3 in D:
        if p1==p3 or p2==p3: continue
        f[side(p1,p2,p3)]+=1
      if min(f)==0:
        n-=1
        break
  print n

Submission status: Accepted

Solution code:
import sys
def side(p1, p2, p3):
  y1,x1=p1
  y2,x2=p2
  y3,x3=p3
  return (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>0
while 1:
  n=input()
  if n==0:break
  D=sorted([list(input()) for i in range(n)])
  p1=D[0]
  D1=D[:]
  while True:
    c=0
    for p2 in D1:
      if p1==p2:continue
      f=[0,0]
      for p3 in D:
        if p1==p3 or p2==p3: continue
        f[side(p1,p2,p3)]+=1
      if f[0]==0:break
    p1=p2
    D1.remove(p2)
    if p2==D[0]:break
  print len(D1)

Submission status: Accepted

Solution code:
import sys
def side(p1, p2, p3):
  y1,x1=p1
  y2,x2=p2
  y3,x3=p3
  return (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>0
while 1:
  n=input()
  if n==0:break
  D=sorted([list(input()) for i in range(n)])
  p1=D[0]
  D1=D[:]
  while True:
    c=0
    for p2 in D1:
      if p1==p2:continue
      f=[0,0]
      for p3 in D[::-1]:
        if p1==p3 or p2==p3: continue
        f[side(p1,p2,p3)]+=1
      if f[0]==0:break
    p1=p2
    D1.remove(p2)
    if p2==D[0]:break
  print len(D1)

Submission status: Accepted

Solution code:
import sys
def side(p1, p2, p3):
  y1,x1=p1
  y2,x2=p2
  y3,x3=p3
  return (x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)>0
while 1:
  n=input()
  if n==0:break
  D=sorted([list(input()) for i in range(n)])
  p1=D[0]
  D1=D[:]
  while True:
    for p2 in D1:
      if p1==p2:continue
      for p3 in D[::-1]:
        if p1==p3 or p2==p3: continue
        if side(p1,p2,p3)==0:break
      else:break
    p1=p2
    D1.remove(p2)
    if p2==D[0]:break
  print len(D1)

Submission status: Accepted

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:continue
    y3,x3=p3
    if (x3-x1)*dy-dx*(y3-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: Accepted

Solution code:
import sys
def side(p1,p2):
  global D
  y1,x1=p1
  dy=p2[0]-y1
  dx=p2[1]-x1
  for p3 in D[::-1]:
    if p1==p3 or p2==p3:pass
    elif (p3[1]-x1)*dy-dx*(p3[0]-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: Accepted

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 (p3[1]-x1)*dy-dx*(p3[0]-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: Accepted

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]:
    y3,x3=p3
    if p1==p3 or p2==p3:pass
    elif (x3-x1)*dy-dx*(y3-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: Accepted

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]:
    y3,x3=p3
    if p1==p3 or p2==p3:continue
    if (x3-x1)*dy-dx*(y3-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: Accepted

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:continue
    if (p3[1]-x1)*dy-dx*(p3[0]-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: Accepted

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:
    if p1!=p3 and p2!=p3 and (p3[1]-x1)*dy-dx*(p3[0]-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]
  while 1:
    for p2 in D:
      if p1!=p2 and side(p1,p2):break
    p1=p2
    D.remove(p2)
    if p2==p:break
  print len(D)

Submission status: Accepted

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:
    if p1==p3 or p2==p3:continue
    if (p3[1]-x1)*dy-dx*(p3[0]-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]
  while 1:
    for p2 in D:
      if p1!=p2 and side(p1,p2):break
    p1=p2
    D.remove(p2)
    if p2==p:break
  print len(D)

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 convex(v,n):
	k = 0
	d = []
	u = []
	for i in range(n):
		d.append(i)
		u.append(i)
		while len(d) > 2:
			if a(v[d[-3]],v[d[-2]]) < a(v[d[-2]],v[d[-1]]):
				del d[-2]
			else:
				break
		while len(u) > 2:
			if a(v[u[-3]],v[u[-2]]) > a(v[u[-2]],v[u[-1]]):
				del u[-2]
			else:
				break
	return n - len(set(d+u))
	
while 1:
	n = 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:
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 = 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:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def cross3(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

EPS = -1e-9
def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs)>1 and cross3(qs[-1], qs[-2], p) > -EPS:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs)>t and cross3(qs[-1], qs[-2], p) > -EPS:
            qs.pop()
        qs.append(p)
    return qs

def solve():
    N = int(readline())
    if N == 0:
        return False
    P = [list(map(float, readline().split(","))) for i in range(N)]
    P.sort()
    Q = convex_hull(P)
    write("%d\n" % (N - len(Q) + 1))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
#凸包を求める

def quickhull(l,r,s,k):
    if not s:
        return
    su = []
    sd = []
    a = (r[0]-l[0],r[1]-l[1])
    for x,y in s:
        b = (x-l[0],y-l[1])
        cro = cross(a,b)
        if cro > 0:
            su.append((x,y)) #上半分
        elif cro < 0:
            sd.append((x,y)) #下半分

    if su:
        c,d = direction(l,r,su[0])
        p = su[0]
        for i in range(1,len(su)):
            c_,d_ = direction(l,r,su[i])
            if c*d_ < c_*d:
                c,d = c_,d_
                p = su[i]
        k.append(tuple(p)) #もっとも離れた点を凸包の頂点に追加
        b = (l[0]-p[0],l[1]-p[1])
        c = (p[0]-r[0],p[1]-r[1])
        s1 = []
        s2 = []
        for x,y in su:
            b_ = (x-p[0],y-p[1])
            c_ = (x-r[0],y-r[1])
            cro_b,cro_c = cross(b,b_),cross(c,c_)
            if cro_b >= 0 and cro_c >= 0: #三角形内部判定
                continue
            else:
                if cro_b < 0:
                    s1.append((x,y))
                elif cro_c < 0:
                    s2.append((x,y))
        quickhull(l,p,s1,k) #再帰
        quickhull(p,r,s2,k)

    if sd:
        c,d = direction(l,r,sd[0])
        p = sd[0]
        for i in range(1,len(sd)):
            c_,d_ = direction(l,r,sd[i])
            if c*d_ < c_*d:
                c,d = c_,d_
                p = sd[i]
        k.append(tuple(p)) #もっとも離れた点を凸包の頂点に追加
        b = (l[0]-p[0],l[1]-p[1])
        c = (p[0]-r[0],p[1]-r[1])
        s1 = []
        s2 = []
        for x,y in sd:
            b_ = (x-p[0],y-p[1])
            c_ = (x-r[0],y-r[1])
            cro_b,cro_c = cross(b,b_),cross(c,c_)
            if cro_b <= 0 and cro_c <= 0: #三角形内部判定(ベクトルの向きにより上下で判定が異なることに注意)
                continue
            else:
                if cro_b > 0:
                    s1.append((x,y))
                elif cro_c > 0:
                    s2.append((x,y))
        quickhull(l,p,s1,k) #再帰
        quickhull(p,r,s2,k)
    return k

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

def direction(l,r,p): #点と直線の距離
    a = r[1]-l[1]
    b = l[0]-r[0]
    return (a*(p[0]-l[0])+b*(p[1]-l[1]))**2, a**2+b**2 #分子の2乗,分母の2乗
while 1:
    n = int(input())
    if n == 0:
        break
    s = [[float(x) for x in input().split(",")] for i in range(n)]
    s.sort()
    l = tuple(s.pop(0))
    r = tuple(s.pop(-1))
    k = quickhull(l,r,s,[l,r])
    print(n-len(k))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def ccw(a, b, c):
    ax = b[0] - a[0]
    ay = b[1] - a[1]
    bx = c[0] - a[0]
    by = c[1] - a[1]
    t = ax*by - ay*bx;
    if t > 0:
        return 1
    if t < 0:
        return -1
    if ax*bx + ay*by < 0:
        return 2
    if ax*ax + ay*ay < bx*bx + by*by:
        return -2
    return 0

def convex_hull(ps):
    n = len(ps)
    k = 0
    ps.sort()
    ch = [[-1,-1] for _ in range(n*2)]
    for i in range(n):
        while k >= 2 and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    t = k + 1
    for i in range(n-2,-1,-1):
        while k >= t and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    ch = ch[:k-1]
    return ch

def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        a = [list(map(float, S().split(','))) for _ in range(n)]
        r = convex_hull(a)
        rr.append(n-len(r))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
    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) > 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: Runtime Error

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().splirt(',')) for i in range(n)]
    v=sorted(sorted(v,key=lambda x:x[1]))
    print convex(v,n)

Submission status: Runtime Error

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
    y3,x3=p3
    elif (x3-x1)*dy-dx*(y3-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: Runtime Error

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:]
        la,ra = DC(la),DC(ra)
        # Conquer
        if len(la) == 1 or len(ra) == 1:
            return la+ra
        else:
            while f(ra[1][0],ra[1][1],la[-1][0],la[-1][1],ra[0][0],ra[0][1]) > 0:
                ra.pop(0)
            while 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: Runtime Error

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 f(ra[1][0],ra[1][1],la[-1][0],la[-1][1],ra[0][0],ra[0][1]) > 0 and len(ra) > 1:
            ra.pop(0)
        while f(la[-2][0],la[-2][1],ra[0][0],ra[0][1],la[-1][0],la[-1][1]) > 0 and len(la) > 1:
            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))