Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Cheat at Math
Time Limit: 10000MSMemory Limit: 1024K
Total Submissions: 181Accepted: 37
Case Time Limit: 1000MS

Description

In Nanjing, a great many students cheat at Mathematics Olympiad contest. Some of them stole the problems. What is worse, some others, like K.W., could even modify the answer sheet to enlarge his scoring. Even though, he is waiting for your help to solve such a complex puzzle, for he cannot solve it himself.

There are four kinds of arcs on the plane: (4 denotes a full circle, 3 denotes ¾ a circle, 2 denotes half a circle, 1 denotes ¼ a circle)

All of the arcs are facing leftwards (as the picture above, one should not rotate them). You are given N <= 1000 arcs on the plane, how many regions are formed out by them (several close regions including the outmost open region)? See the following example:

Eight regions are formed out with six arcs.

Input

One non-negative integer N <= 1000 occupies the first line. On each of the 2nd ~ (N + 1)-th line, there will be four integers Xi, Yi, Ri, Ti. An arc of type Ti (1 <= Ti <= 4) with radius of Ri is situated on coordinate (Xi, Yi). We have –5000 <= Xi, Yi <= 5000, 1 <= Ri <= 5000.

Output

A single line denoting the number of regions formed by those arcs.

Sample Input

6
-1 0 2 4
1 0 2 4
0 0 3 4
7 0 2 4
9 0 2 3
11 0 2 2

Sample Output

8

Hint

Pay attention to the limit of memory.

Source

POJ Monthly--2006.03.26,Zeyuan Zhu,Modified from Timus 1429

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator