Problem:


Area of Polygons

Polygons are the most fundamental objects in geometric processing.
Complex figures are often represented and handled as polygons
with many short sides.
If you are interested in the processing of geometric data,
you'd better try some programming exercises about basic
operations on polygons.

Your job in this problem is to write a program that computes the area of polygons.

A polygon is represented by a sequence of points that are its vertices.
If the vertices p1, p2, ..., pn are given, line segments connecting
pi and pi+1 (1 n and p1 is also a side of the polygon.

You can assume that the polygon is not degenerate.
Namely, the following facts can be assumed without any input data checking.

No point will occur as a vertex more than once.

Two sides can intersect only at a common endpoint (vertex).

The polygon has at least 3 vertices.

Note that the polygon is not necessarily convex.
In other words, an inner angle may be larger than 180 degrees.

Input

The input contains multiple data sets, each representing a polygon.
A data set is given in the following format.

   n
   x1 y1
   x2 y2
   ...
   xn yn

The first integer n is the number of vertices,
such that 3 i is given by (xi, yi).
xi and yi are integers between 0 and 1000 inclusive.
The coordinates of vertices are given in the order
of clockwise visit of them.

The end of input is indicated by a data set with 0 as the value of n.

Output

For each data set, your program should output its sequence number
(1 for the first data set, 2 for the second, etc.) and the area of the polygon separated by a single space. The area should be printed with one digit to the right of the decimal point.

The sequence number and the area should be printed on the same line.
Since your result is checked by an automatic grading program,
you should not insert any extra characters nor lines on the output.

Sample Input

3
1 1
3 4
6 0

7
0 0
10 10
0 20
10 30
0 40
100 40
100 0

0

Output for the Sample Input

1 8.5
2 3800.0



Sample input:
3
1 1
3 4
6 0

7
0 0
10 10
0 20
10 30
0 40
100 40
100 0

0


Sample output:
1 8.5
2 3800.0

Submission status: Wrong Answer

Solution code:
c=0
while True:
    n=raw_input()
    if not n:
        break
    c+=1
    x0, y0=map(int,raw_input().split())
    prev_x, prev_y=x0, y0
    tmp=0
    for i in range(int(n)-1):
        x,y=map(int,raw_input().split())
        tmp+=prev_x*y - prev_y*x
        prev_x, prev_y=x, y
    tmp+=prev_x*y0 - prev_y*x0
    print c, 0.5*abs(tmp)

Submission status: Wrong Answer

Solution code:
import sys

print("hello")

Submission status: Wrong Answer

Solution code:
while 1:
    n=int(input())
    if n==0:break
    p=[complex(*map(int,input().split())) for _ in range(n)]
    s,pre=0,p[0]
    while p:
        now=p.pop()
        s+=now.real*pre.imag-now.imag*pre.real
        pre=now
    print(abs(s)/2);input()

Submission status: Wrong Answer

Solution code:
def convex(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    c= v1[0]*v2[1]-v1[1]*v2[0]
    return c

def area(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    return abs(v1[0]*v3[1]-v1[1]*v3[0])/2.

def nopoints(Pset,P):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    CPv=[ [p[0]-Pset[0][0],p[1]-Pset[0][1]] for p in P if p not in Pset]
    #print CPv
    for pv in CPv:
        rdet=1./(v1[0]*v3[1] - v1[1]*v3[0])
        t1=rdet*( v3[1]*pv[0]-v3[0]*pv[1])
        t2=rdet*(-v1[1]*pv[0]+v1[0]*pv[1])
        #print pv, v1, v3, t1,t2
        if (t1>=0 and t2>=0 and t1+t2<=1 ):
            return 0
            break
    return 1


while(1):
    n=int(raw_input())
    if n==0:        break
    P=[]
    for i in range(n):
        P.append([int(x) for x in raw_input().split()])
    ans=0
    while(len(P)>=3):
        for i in range(len(P)-2):
            Pset=P[i:i+3]
            c= convex(Pset)
            if c<=0:
                if c==0:
                    del P[i+1]
                    break
                elif nopoints(Pset,P[:]):
                    ans+=area(Pset)
                    del P[i+1]
                    break
        else:
            print 'err',P
            break
    print ans
    raw_input()

Submission status: Wrong Answer

Solution code:
while True:
    n = raw_input()
    if n == "0":
        break
    l = []
    for i in xrange(int(n)):
        l.append(map(float, raw_input().split()))
    raw_input()
    a = 0
    tmp = l[0]
    for i in l:
        a += (i[1]+tmp[1])*(i[0]-tmp[0])/2.0
        tmp = i
    print a

Submission status: Wrong Answer

Solution code:
while True:
    n = raw_input()
    if n == "0":
        break
    l = []
    for i in xrange(int(n)):
        l.append(map(float, raw_input().split()))
    raw_input()
    a = 0
    tmp = l[-1]
    for i in l:
        a += (i[1]+tmp[1])*(i[0]-tmp[0])/2.0
        tmp = i
    print a

Submission status: Time Limit Exceeded

Solution code:
def convex(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    c= v1[0]*v2[1]-v1[1]*v2[0]
    return c<=0

def area(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    return abs(v1[0]*v3[1]-v1[1]*v3[0])/2.

while(1):
    n=int(raw_input())
    if n==0:        break
    P=[]
    for i in range(n):
        P.append([int(x) for x in raw_input().split()])
    ans=0
    while(len(P)>=3):
        for i in range(len(P)-2):
            Pset=P[i:i+3]
            if convex(Pset):
                ans+=area(Pset)
                del P[i+1]
                break
    print ans
    raw_input()

Submission status: Accepted

Solution code:
# AOJ 1100: Area of Polygons
# Python3 2018.7.14 bal4u

from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

def calc_area(pp):
	n = len(pp)
	if n < 3: return 0
	s = 0
	for i in range(n):
		s += (pp[i].real-pp[(i+1)%n].real)*(pp[i].imag+pp[(i+1)%n].imag)
	return abs(s)/2

cno = 0
while True:
	n = input()
	if n == '': n = input()
	n = int(n);
	if n == 0: break
	pp = []
	for i in range(n):
		x, y = map(int, input().split())
		pp.append(complex(x, y))
	cno += 1
	print(cno, Decimal(str(calc_area(pp))).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP))

Submission status: Accepted

Solution code:
# AOJ 1100: Area of Polygons
# Python3 2018.7.14 bal4u

from decimal import Decimal, ROUND_HALF_UP

def calc_area(pp):
	n, s = len(pp), 0
	for i in range(n): s += (pp[i].real-pp[(i+1)%n].real)*(pp[i].imag+pp[(i+1)%n].imag)
	return abs(s)/2

cno = 0
while True:
	n = int(input())
	if n == 0: break
	pp = [complex(*map(int, input().split())) for i in range(n)]
	input()
	cno += 1
	print(cno, Decimal(str(calc_area(pp))).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP))

Submission status: Accepted

Solution code:
c=0
while True:
    n=input()
    if n==0:
        break
    c+=1
    x0, y0=map(int,raw_input().split())
    prev_x, prev_y=x0, y0
    tmp=0
    for i in range(n-1):
        x,y=map(int,raw_input().split())
        tmp+=prev_x*y - prev_y*x
        prev_x, prev_y=x, y
    tmp+=prev_x*y0 - prev_y*x0
    print c, 0.5*abs(tmp)
    skip=raw_input()

Submission status: Accepted

Solution code:
from math import sqrt,fabs,ceil,floor,pow,exp,log,sin,cos,tan,asin,acos,atan,atan2,pi
import copy


inf=float("inf")


class Real:
	isLineLike=False
	eps=1e-10
	def __init__(self,x):
		self.x=float(x)
	def __float__(self):
		return self.x
	def __repr__(self):
		return str(self.x)
	def __eq__(self,other):
		return abs( float(self) - float(other) ) <= Real.eps
	def __ne__(self,other):
		return abs( float(self) - float(other) ) > Real.eps
	def __lt__(self,other):
		return float(self) < float(other)
	def __le__(self,other):
		return float(self) <= float(other) + Real.eps
	def __gt__(self,other):
		return float(self) > float(other)
	def __ge__(self,other):
		return float(self) + Real.eps >= float(other)
	def __add__(self,other):
		return Real(float(self)+float(other))
	def __sub__(self,other):
		return Real(float(self)-float(other))
	def __mul__(self,other):
		return Real(float(self)*float(other))
	def __div__(self,other):
		return Real(float(self)/float(other))
	def __mod__(self,other):
		return Real(float(self)%float(other))
	def __pow__(self,c):
		return Real(float(self)**c)
	def __rmul__(self,other):
		return Real(float(other)*float(self))
	def __pos__(self):
		return Real(float(self))
	def __neg__(self):
		return Real(-float(self))
	def __abs__(self):
		return Real(abs(float(self)))

class Angle:	#angle. kaku.
	isLineLike=False
	def __init__(self,th):
		self.th = Real(th)%(2*pi)
	def __float__(self):
		return float(self.th)
	def __repr__(self):
		return "Angle("+str(Real(self))+")"
	def __eq__(self,other):
		return Real(self)==Real(other) or abs(Real(self)-Real(other))==Real(2*pi)
	def isParaWith(self,other):
		return self==other or self==other+pi
	def __add__(self,other):
		return Angle( Real(self) + Real(other) )
	def __sub__(self,other):
		return Angle( Real(self) - Real(other) )
	def __mul__(self,c):
		return Angle( Real(self) * Real(c) )
	def __div__(self,c):
		return Angle( Real(self) / Real(c) )
	def __rmul__(self,c):
		return Angle( Real(c) * Real(self) )
	def __pos__(self):
		return Angle(Real(self))
	def __neg__(self):
		return Angle(-Real(self))
	def __abs__(self):
		return Angle(abs(Real(self)))

class Vector:	#point, vector. ten, bekutoru.
	isLineLike=False
	def __init__(self,x=None,y=None,d=None,th=None):
		if not(x is None) and not(y is None):
			self.setXY(x,y)
		if not(d is None) and not(th is None):
			self.setDTh(d,th)
	def setXY(self,x,y):
		self.x=Real(x);
		self.y=Real(y);
		self.calcFromXY()
	def setDTh(self,d,th):
		self.d=Real(d)
		self.th=Angle(th)
		self.calcFromDTh()
	def calcFromXY(self):
		self.d=sqrt(self.x**2+self.y**2)
		self.th=Angle(atan2(self.y,self.x))
	def calcFromDTh(self):
		self.x=self.d*cos(self.th)
		self.y=self.d*sin(self.th)
	def e(self):
		return self/self.d
	def __eq__(self,other):
		return self.x==other.x and self.y==other.y
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,other):
		return Vector(self.x+other.x, self.y+other.y)
	def __sub__(self,other):
		return Vector(self.x-other.x, self.y-other.y)
	def __mul__(self,c):
		return Vector(self.x*c, self.y*c)
	def __div__(self,c):
		return Vector(self.x/c, self.y/c)
	def __rmul__(self,c):
		return Vector(c*self.x, c*self.y)
	def __pos__(self):
		return Vector(self.x, self.y)
	def __neg__(self):
		return Vector(-self.x, -self.y)
	def __abs__(self):
		return +self.d
	def rotated(self,th):
		return Vector(d=self.d, th=self.th+th)
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def inprod(self,other):
		return self.x*other.x+self.y*other.y
	def outprod(self,other):
		return self.x*other.y-self.y*other.x
	def isOn(self,obj):
		if isinstance(obj,DirSegLine) or isinstance(obj,SegLine):
			return obj.ap==self or obj.bp==self or (obj.th==(self-obj.ap).th and obj.th==(obj.bp-self).th)
		if isinstance(obj,HalfLine):
			return obj.ap==self or obj.th==(self-obj.ap).th
		if isinstance(obj,Line):
			return obj.th==(self-obj.ap).th or obj.th==(obj.bp-self).th
		if isinstance(obj,Circle):
			return abs(self-obj.p)==obj.d
	def isIn(self,obj):
		if isinstance(obj,Circle):
			return abs(self-obj.p)<obj.d
	def isOut(self,obj):
		if isinstance(obj,Circle):
			return abs(self-obj.p)>obj.d
	def __repr__(self):
		return "Vector("+str(self.x)+", "+str(self.y)+")"

Point=Vector

class DirSegLine:	#directed line segment. yuukou senbun.
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.d = abs(self.dv)
		self.th = +self.dv.th
	def __eq__(self,other):
		return self.ap==other.ap and self.bp==other.bp
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return DirSegLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return DirSegLine(self.ap-v, self.bp-v)
	def __abs__(self):
		return +self.d
	def rotated(self,th):
		return DirSegLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "DirSegLine(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class SegLine:	#line segmeny. senbun.
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.d = abs(self.dv)
		self.th = +self.dv.th
	def __eq__(self,other):
		return (self.ap==other.ap and self.bp==other.bp) or (self.ap==other.bp and self.bp==other.ap)
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return SegLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return SegLine(self.ap-v, self.bp-v)
	def __abs__(self):
		return +self.d
	def rotated(self,th):
		return SegLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "SegLine(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class HalfLine:
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None,th=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
		if not(ap is None) and not(th is None): self.setApBp(ap, ap+Vector(d=1,th=th))
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.th = +self.dv.th
	def __eq__(self,other):
		return self.ap==other.ap and self.th==other.th
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return HalfLine(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return HalfLine(self.ap-v, self.bp-v)
	def rotated(self,th):
		return HalfLine(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "HalfLine(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class Line:
	isLineLike=True
	def __init__(self,ap=None,bp=None,dv=None,th=None):
		if not(ap is None) and not(bp is None): self.setApBp(ap, bp)
		if not(ap is None) and not(dv is None): self.setApBp(ap, ap+dv)
		if not(bp is None) and not(dv is None): self.setApBp(bp-dv, bp)
		if not(ap is None) and not(th is None): self.setApBp(ap, ap+Vector(d=1,th=th))
		if not(bp is None) and not(th is None): self.setApBp(bp-Vector(d=1,th=th), bp)
		if ap.isLineLike: self.setApBp(ap.ap,ap.bp)
	def setApBp(self,ap,bp):
		self.ap=+ap
		self.bp=+bp
		self.calcFromApBp()
	def calcFromApBp(self):
		self.dv = self.bp - self.ap
		self.th = +self.dv.th
	def __eq__(self,other):
		#return ( self.ap==other.ap or self.ap==other.bp or (self.ap-other.ap).isParaWith(other.dv) )	\
		#	and( self.bp==other.ap or self.bp==other.bp or (self.bp-other.bp).isParaWith(other.dv) )
		return self.ap.isOn(other) and self.bp.isOn(other)
	def isParaWith(self,other):
		return self.th.isParaWith(other.th)
	def __add__(self,v):
		return Line(self.ap+v, self.bp+v)
	def __sub__(self,v):
		return Line(self.ap-v, self.bp-v)
	def rotated(self,th):
		return Line(self.ap.rotated(th), self.bp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "Line(ap="+str(self.ap)+", bp="+str(self.bp)+")"

class Circle:
	isLineLike=False
	def __init__(self,p,d):
		self.setPD(p,d)
	def setPD(self,p,d):
		self.p=+p
		self.d=Real(d)
	def __eq__(self,other):
		return self.p==other.p and self.d==other.d
	def __add__(self,v):
		return Circle(self.p+v, +self.d)
	def __sub__(self,v):
		return Circle(self.p-v, +self.d)
	def rotated(self,th):
		return Circle(self.p.rotated(th), +self.d)
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def __repr__(self):
		return "Circle(p="+str(self.p)+", d="+str(self.d)+")"

class Triangle:
	isLineLike=False
	def __init__(self,ap,bp,cp):
		self.setApBpCp(ap,bp,cp)
	def setApBpCp(self,ap,bp,cp):
		self.ap=+ap
		self.bp=+bp
		self.cp=+cp
		self.calcFromApBpCp(ap, bp, cp)
	def calcFromApBpCp(self,ap,bp,cp):
		self.ae=SegLine(bp,cp)
		self.be=SegLine(cp,ap)
		self.ce=SegLine(ap,bp)
	def __eq__(self,other):
		return (self.ap==other.ap and self.bp==other.bp and self.cp==other.cp) \
			or (self.ap==other.bp and self.bp==other.cp and self.cp==other.ap) \
			or (self.ap==other.cp and self.bp==other.ap and self.cp==other.bp)
	def __add__(self,v):
		return Triangle(self.ap+v,self.bp+v,self.cp+v)
	def __sub__(self,v):
		return Triangle(self.ap-v,self.bp-v,self.cp-v)
	def rotated(self,th):
		return Triangle(self.ap.rotated(th),self.bp.rotated(th),self.cp.rotated(th))
	def rotatedWithCenter(self,th,p):
		return (self-p).rotated(th)+p
	def dirArea(self):
		return (self.ae).outprod(self.be)/2 	#=(axb+bxc+cxa)/2
	def area(self):
		return abs(self.dirArea())
	def gravityCenter(self):	#juushin
		return (self.ap+self.bp+self.cp)/3
	def innerCenter(self):		#naishin
		return crossPoints(angleBisector(self.ae,self.be), angleBisector(self.be,self.ce))[0]
	def exterCenter(self):		#gaishin
		return crossPoints(perpendicularBisector(self.ae), perpendicularBisector(self.be))[0]
	def orthoCenter(self):		#suishin
		return crossPoints(perpendicular(self.ap,self.ae), perpendicular(self.bp,self.be))[0]
	def __repr__(self):
		return "Triangle("+str(self.ap)+", "+str(self.bp)+", "+str(self.cp)+")"

class Polygon:
	def __init__(self,ps):
		self.ps=copy.deepcopy(ps)
		self.uniquenize()
		self.checkSimplicity()
		self.checkConvexity()
	def uniquenize(self):
		nps = []
		for p in self.ps:
			if len(nps)==0:
				nps.append(p)
				continue
			if nps[-1]==p:
				pass
			else:
				nps.append(p)
		if len(nps)>1:
			if nps[0]==nps[-1]:
				nps.pop(0)
		self.ps=nps
	def __eq__(self,other):
		sps=copy.copy(self.ps)
		ops=copy.copy(other.ps)
		if len(sps)!=len(ops): return False
		for i in xrange(0,len(sps)):
			icchi=True
			for j in xrange(0,len(sps)):
				if sps[i]==sps[j]:
					pass
				else:
					icchi=False
					break
			if icchi: return True
			else: continue
		return False
	def __add__(self,v):
		g=Polygon(self.ps)
		for p in g:
			p+=v
		return g
	def __sub__(self,v):
		g=Polygon(self.ps)
		for p in g:
			p-=v
		return g
	def rotated(self,th):
		g=Polygon(self.ps)
		for p in g:
			p=p.rotated(th)
		return g
	def rotatedWithCenter(self,th,cp):
		g=Polygon(self.ps)
		for p in g:
			p=p.rotatedWithCenter(th,cp)
		return g
	def checkSimplicity(self):
		self.isSimple=True
	def checkConvexity(self):
		self.isConvex=True
	def getConvexHull(self):
		return None
	def dirArea(self):
		if self.isSimple:
			re=Real(0)
			for j in xrange(0,len(self.ps)):
				re += self.ps[j-1].outprod(self.ps[j])/2
			return re
	def area(self):
		return abs(self.dirArea())
	def __repr__(self):
		re="Polygon(["
		for p in self.ps:
			re += str(p)+", "
		re=re.rstrip(", ")
		re+="])"
		return re

def crossPoints(m,n):
	if m.isLineLike and n.isLineLike:
		c = m.dv.outprod(n.dv)
		if c==0: return []
		s = n.dv.outprod(m.ap-n.ap) / c
		t = m.dv.outprod(n.ap-m.ap) / c
		if (     ((isinstance(m,DirSegLine) or isinstance(m,SegLine)) and 0<=s<=1)	\
			or   (isinstance(m,HalfLine) and 0<=s)									\
			or   (isinstance(m,Line))												\
		   )and( ((isinstance(m,DirSegLine) or isinstance(m,SegLine)) and 0<=t<=1)	\
			or   (isinstance(m,HalfLine) and 0<=t)									\
			or   (isinstance(m,Line))												\
			):
			return [m.ap+m.dv*s]
		else:
			return []
	elif m.isLineLike and isinstance(n,Circle):
		re=[]
		l=perpendicular(n.p, m)
		if l.bp.isOn(n):
			p=+l.bp
			if p.isOn(m): re.append(p)
			return re
		if l.bp.isOut(n):
			return re
		if l.bp.isIn(n):
			r=sqrt(n.d**2-l.d**2)
			p1 = l.bp+Vector(d=r,th=m.th)
			p2 = l.bp-Vector(d=r,th=m.th)
			if p1.isOn(m): re.append(p1)
			if p2.isOn(m): re.append(p2)
			return re
	elif isinstance(n,Circle) and m.isLineLike:
		return crossPoints(n, m)
	elif isinstance(m,Circle) and isinstance(n,Circle):
		d = abs(m.p-n.p)
		if d==0 and m.d==n.d:	#itchi
			return []
		if d== m.d-n.d:			#naisetsu(n in m)
			return [(n.p*m.d-m.p*n.d)/(m.d-n.d)]
		if d < m.d-n.d:			#naihou(n in m)
			return []
		if d== n.d-m.d:			#naisetsu(m in n)
			return [(m.p*n.d-n.p*m.d)/(n.d-m.d)]
		if d < n.d-m.d:			#naihou(n in m)
			return []
		if d== m.d+n.d:			#gaisetsu
			return [(m.p*n.d+n.p*m.d)/(m.d+n.d)]
		if d > m.d+n.d:			#hanareteru
			return []
		if d < m.d+n.d:
			x = (d**2+m.d**2-n.d**2)/(2*d)
			y = sqrt(m.d**2-x**2)
			th = (n.p-m.p).th
			v1 = Vector(x,y)
			v1 = v1.rotated(th)
			v2 = Vector(x,-y)
			v2 = v2.rotated(th)
			return [m.p+v1, m.p+v2]

def perpendicular(p,m):
	ap=p
	th=m.th+pi/2
	bp=crossPoints(Line(m.ap,m.bp), Line(ap=ap,th=th))[0]
	re = DirSegLine(ap,bp)
	if not re.th.isParaWith(th): re.th=th
	return re

def angleBisector(m,n):
	if m.isParaWith(n):
		return Line(ap=(m.ap+n.ap)/2,th=m.th)
	else:
		return Line(ap=crossPoints(Line(m.ap,m.bp),Line(n.ap,n.bp))[0], th = (m.th+n.th)/2)

def perpendicularBisector(m):
	return Line(ap=(m.ap+m.bp)/2,th=m.th+pi/2)



n=0
while True:
	n+=1
	pl=int(raw_input())
	if pl==0: break
	ps=[]
	for i in xrange(pl):
		px,py = tuple(map(int, raw_input().split()))
		ps.append(Vector(px,py))
	g = Polygon(ps)
	print n, g.area()
	raw_input()

Submission status: Accepted

Solution code:
num = 1

while True:
    n = int(input())
    if not n:
        break
    x0, y0 = map(float, input().split())
    prx, pry = x0, y0
    area = 0
    for _ in range(n - 1):
        x, y = map(float, input().split())
        area += (prx * y - x * pry)
        prx, pry = x, y
    area += (prx * y0 - x0 * pry)
    area /= 2
    print(num, abs(area))
    num += 1
    input()

Submission status: Accepted

Solution code:
q = 1
while True:
  n = int(raw_input())
  if n == 0: break
  x = [0] * n
  y = [0] * n
  for i in xrange(n):
    x[i],y[i] = map(float, raw_input().split())
  S = 0
  for i in xrange(n):
    S += x[i]*y[(i+1)%n] - x[(i+1)%n]*y[i]
  if S < 0: S = -S
  print "%d %.1f" % (q, S/2)
  q += 1
  raw_input()

Submission status: Accepted

Solution code:
from os import sys
n = int(input())
c = 1
while True:
    if n == 0:
        sys.exit(0)
    X = 0
    Y = 0
    ox = 0
    oy = 0
    esquerda = 0
    direita = 0
    for i in range(0,n):
        cx, cy = input().split(' ')
        cx = int(cx)
        cy = int(cy)
        if i == 0:
            X = cx
            Y = cy
        direita += ox * cy
        esquerda += oy * cx
        ox = cx
        oy = cy

    esquerda += X * oy
    direita += Y * cx
    s = direita - esquerda
    if s < 0:
        s = esquerda - direita
    s = s/2
    print("%d %.1f" %(c,s))
    c += 1
    n = input()
    if n == '':
        n = input()
    n = int(n)

Submission status: Accepted

Solution code:
c=0
while 1:
    n=int(input())
    if n==0:break
    c+=1
    p=[complex(*map(int,input().split())) for _ in range(n)]
    s,pre=0,p[0]
    while p:
        now=p.pop()
        s+=now.real*pre.imag-now.imag*pre.real
        pre=now
    print(c,abs(s)/2);input()

Submission status: Accepted

Solution code:
idx = 1
while True:
    n = int(input())
    if n==0: break
    x = []
    y = []
    for _ in range(n):
        a,b = map(int,input().split())
        x.append(a)
        y.append(b)
    x.append(x[0])
    y.append(y[0])

    s = 0.0
    for i in range(n):
        s += x[i]*y[i+1] - x[i+1]*y[i]
    print(idx, abs(s/2))
    idx += 1
    input()

Submission status: Accepted

Solution code:
def convex(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    c= v1[0]*v2[1]-v1[1]*v2[0]
    return c

def area(Pset):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    return abs(v1[0]*v3[1]-v1[1]*v3[0])/2.

def nopoints(Pset,P):
    v1=[Pset[1][0]-Pset[0][0],Pset[1][1]-Pset[0][1]]
    v2=[Pset[2][0]-Pset[1][0],Pset[2][1]-Pset[1][1]]
    v3=[Pset[2][0]-Pset[0][0],Pset[2][1]-Pset[0][1]]
    CPv=[ [p[0]-Pset[0][0],p[1]-Pset[0][1]] for p in P if p not in Pset]
    #print CPv
    for pv in CPv:
        rdet=1./(v1[0]*v3[1] - v1[1]*v3[0])
        t1=rdet*( v3[1]*pv[0]-v3[0]*pv[1])
        t2=rdet*(-v1[1]*pv[0]+v1[0]*pv[1])
        #print pv, v1, v3, t1,t2
        if (t1>=0 and t2>=0 and t1+t2<=1 ):
            return 0
            break
    return 1

an=1
while(1):
    n=int(raw_input())
    if n==0:        break
    P=[]
    for i in range(n):
        P.append([int(x) for x in raw_input().split()])
    ans=0
    while(len(P)>=3):
        for i in range(len(P)-2):
            Pset=P[i:i+3]
            c= convex(Pset)
            if c<=0:
                if c==0:
                    del P[i+1]
                    break
                elif nopoints(Pset,P[:]):
                    ans+=area(Pset)
                    del P[i+1]
                    break
        else:
            print 'err',P
            break
    print an, ans
    raw_input()
    an+=1

Submission status: Accepted

Solution code:
# coding: utf-8

def mul(p1, p2):
    return (p1[0] - p2[0]) * (p1[1] + p2[1]) * 1.0

n = input()
cnt = 1

while n != 0:
    data = []
    for i in range(n):
        data.append(map(int, raw_input().split()))
    data.append(data[0])

    areaSum = 0.0
    for i in range(n):
        areaSum = areaSum + mul(data[i],data[i+1])
    print cnt, abs(areaSum) / 2
    cnt = cnt + 1
    
    raw_input()
    n = input()

Submission status: Accepted

Solution code:
index = 1

while True:
    n = int(input())
    if n == 0:
        break
    else:
        area = 0
        X = []
        Y = []
        for i in range(n):
            x, y = map(int, input().split())
            X.append(x)
            Y.append(y)
        for i in range(1, n-1):
            area += ((X[i] - X[0]) * (Y[i+1] - Y[0]) - (X[i+1] - X[0]) * (Y[i] - Y[0])) / 2
    if area < 0:
        print("{0} {1}".format(index, -area))
    else:
        print("{0} {1}".format(index, area))
    blank = input()
    index += 1

Submission status: Accepted

Solution code:

def shoelace(A):
    ret = 0

    for idx in range(1, len(A)):
        left = A[idx - 1]
        right = A[idx]
        ret += left[0] * right[1] - left[1] * right[0]

    ret += A[-1][0] * A[0][1] - A[-1][1] * A[0][0]

    return abs(ret) / 2


index = 1

while True:
    N = int(input())
    if N == 0:
        break

    A = []

    for i in range(N):
        A.append([int(elem) for elem in input().split()])

    print(index, shoelace(A))
    index += 1

    input()

Submission status: Accepted

Solution code:
def cp(a, b):return a[0] * b[1] - a[1] * b[0]
c = 1
while 1:
    n = int(input())
    if n == 0:break
    p = [tuple(map(int, input().split())) for _ in range(n)]
    input()
    s = 0
    for i in range(n):s += cp(p[i], p[i - 1])
    s = abs(s / 2)
    print("{} {}".format(c,s))
    c += 1

Submission status: Accepted

Solution code:
def area(p,q,r):
    a = [x-y for x,y in zip(r,p)]
    b = [x-y for x,y in zip(q,p)]
    return (a[0]*b[1]-a[1]*b[0]) / 2

S = []

while True:
    string = input()
    if string == '':
        continue
    elif int(string) == 0:
        break
    else:
        n = int(string)
        v = []
        for _ in range(n):
            v.append([int(x) for x in input().split()])
        s = 0
        for i in range(1,n-1):
            s += area(v[0],v[i],v[i+1])
        S.append(round(s,1))

for i,x in enumerate(S):
    print(i+1, x)

Submission status: Accepted

Solution code:
cnt=1
while True:
    n=input()
    if n==0:break
    data=[map(int,raw_input().split()) for i in range(n)]
    data.append(data[0])
    print cnt,sum((data[i][0]-data[i+1][0])*(data[i][1]+data[i+1][1]) for i in \
range(n))/(-2.0)
    cnt+=1
    skip=raw_input()

Submission status: Accepted

Solution code:
c = 0
while True:
    c += 1
    n = raw_input()
    if n == "0":
        break
    l = []
    for i in xrange(int(n)):
        l.append(map(float, raw_input().split()))
    raw_input()
    a = 0
    tmp = l[-1]
    for i in l:
        a += (i[1]+tmp[1])*(i[0]-tmp[0])/2.0
        tmp = i
    print "{0} {1}".format(c, a)

Submission status: Accepted

Solution code:
cross=lambda a1, b1, a2, b2: a1*b2-a2*b1
try:
	T=0
	while True:
		T+=1
		n=int(raw_input())
		if n==0: break
		a=[[float(e) for e in raw_input().split()] for i in range(n)]
		s=0
		t=0
		for i in range(n-1):
			x=cross(a[i][0],a[i][1],a[i+1][0],a[i+1][1])
			if x>0: s+=abs(x)/2
			else: t+=abs(x)/2
		x=cross(a[n-1][0],a[n-1][1],a[0][0],a[0][1])
		if x>0: s+=abs(x)/2
		else: t+=abs(x)/2
		print('%d %.1f'%(T,abs(s-t)))
		raw_input()
except EOFError:
	pass

Submission status: Accepted

Solution code:
c = 1
while 1:
	n = input()
	if n == 0: break
	xy = [map(int,raw_input().split()) for i in range(n)]
	xy.append(xy[0])
	print c,abs(sum(xy[i][0]*xy[i+1][1] - xy[i+1][0]*xy[i][1] for i in range(n)))/2.0
	c += 1
	raw_input()

Submission status: Accepted

Solution code:
import sys
if sys.version_info[0]>=3: raw_input=input
cross=lambda a1, b1, a2, b2: a1*b2-a2*b1
try:
	T=0
	while True:
		T+=1
		n=int(raw_input())
		if n==0: break
		a=[[float(e) for e in raw_input().split()] for i in range(n)]
		s=0
		t=0
		for i in range(n-1):
			x=cross(a[i][0],a[i][1],a[i+1][0],a[i+1][1])
			if x>0: s+=abs(x)/2
			else: t+=abs(x)/2
		x=cross(a[n-1][0],a[n-1][1],a[0][0],a[0][1])
		if x>0: s+=abs(x)/2
		else: t+=abs(x)/2
		print('%d %.1f'%(T,abs(s-t)))
		raw_input()
except EOFError:
	pass

Submission status: Accepted

Solution code:
def cal(a,b):
    return a[0]*b[1]-a[1]*b[0]

c=1

while 1:
    N=int(input())
    if N==0:
        break
    p=[tuple(map(int, input().split())) for _ in range(N)]
    input()
    S=0
    for i in range(N):
        S += cal(p[i],p[i-1])
    S=abs(S/2)
    print("{} {}".format(c,S))
    c+=1

Submission status: Accepted

Solution code:
def area(px,py,x,y):
    if py > y:
        py,y = y,py
    return py*(x-px)+(x-px)*abs(y-py)/2

count = 1
while True:
    res = 0
    n = int(input())
    if n == 0:
        break
    px,py = map(int,input().split())
    sx,sy = px,py
    for _ in range(n-1):
        x,y = map(int,input().split())
        res += area(px,py,x,y)
        px,py = x,y
    res += area(px,py,sx,sy)
    print(count,res)
    count += 1
    input()

Submission status: Accepted

Solution code:
def det(a,b):
    return a[0]*b[1] - a[1]*b[0]
cnt = 1
while True :
    n = int(input())
    if n==0:
        break
    dots = []
    std = list(map(int,input().split()))
    for i in range(n-1):
        dots.append(list(map(int,input().split())))
    #print(dots)
   
    dots2 = []
    for dot in dots:
        dot[0] -= std[0]
        dot[1] -= std[1]
        dots2.append(dot)
    #print(dots2)
    area = 0
    for i in range(n-2):
        area += det(dots2[i],dots2[i+1])
    area /= 2
    area = abs(area)
    #print(std)
    print("{} {}".format(cnt,area))
    cnt +=1
    input()