# Box Area - Python

Budget $10-30 USD

- Freelancer
- Jobs
- Python
- Box Area - Python

Bounding Boxes Positions

A rectangle in a 2D plane with non-zero area is called a non-degenerate rectangle. A degenerate rectangle in a 2D plane is effectively a single segment or a point. In this problem we will consider only non-degenerate rectangles.

Axis aligned rectangle is a rectangle each of which sides is parallel to x or y coordinate axis.

Let A and B be two axis aligned rectangles with non-zero area. Depending on their location in the plane, A and B can be in various relative positions. We will divide all possible relative positions of two axis aligned rectangles into 8 cases listed below.

1. A and B are identical.

2. The boundary of one rectangle lies completely in the interior of the other rectangle.

3. The interior of one rectangle lies completely in the interior of the other rectangle and the borders of the rectangles share at least one point.

4. A lies completely outside of B.

5. The interiors of A and B do not intersect and both rectangles share at least one common point on their borders.

6. Exactly one corner point of one rectangle lies in the interior of the other rectangle and simultaneously exactly one corner point of the other rectangle lies in the interior of the first rectangle.

7. For at least one of the rectangles it holds that exactly two of its corner points lie outside the other rectangle.

8. The borders of the rectangles instersect one another in exactly four distinct points.

Note that cases 1. - 8. list all possibilites, that is, the relative position of any two axis aligned rectangles in a plane always falls into one of the categories 1. - 8. Also note that each pair of cases is mutually exclusive, i.e. mutual position of any two rectangles fall into exactly one case 1. - 8. 1

The task

A set of pairwise distinct points in the plane is given. Consider each pair of distinct triples of points which bounding boxes are non-degenerate and decide to which case 1. - 8. the relative position of the two bounding boxes belongs. Count how many pairs fall into each of the cases 1. - 8.

Two triples of points are distinct if they differ in at least one point.

Input

The first input line contains one integer N, the number of input points.

Next, there are N lines, each contains one point coordinates. Each line contains x and y coordinate separated by space.

It holds 4 ≤ N ≤ 20. All coordinates are non-negative and less than 15.

Output

The output contains eight lines, each line corresponds to one of the cases 1. - 8. listed above. The cases are listed in ascending order. The lines contains one integer denoting the number of the case and another integer separated by space and denoting the number of pairs of non-degenerate boundig boxes of points triples which mutual position falls into this particular case.

Example 1

Input

6

1 4

2 1

3 4

4 3

6 2

7 5

Output

1 4

2 4

3 70

4 2

5 18

6 14

7 78

8 0

Example 2

Input

4

1 1

3 6

7 2

4 3

Output

1 0

2 0

3 3

4 0

5 0

6 0

7 3

8 0

Example 3

Input

16

1 1

1 2

1 3

1 4

2 1

2 2

2 3

2 4

3 1

3 2

3 3

3 4

4 1

4 2

4 3

4 4

Output

1 5808

2 208

3 56624

4 4576

5 27984

6 968

7 42704

8 256

P.S. You should improve and use code in Attachment

## Awarded to:

## 14 freelancers are bidding on average $32 for this job

I have experience using R for statistical analysis and machine learning and have worked on various data science projects such as recommender systems with NLP components, data mining with associative rules, etc. I also More

Hi, I have 5+years Experience in Website/Software Design & Website Development. I'm an Expert in: -Frontend & Backend Development -Python -Data Science -Machine Learning -JVM technologies -Jquery, PHP -Ion More

Hello How are you? I've read carefully your job description. I have more than five years experience in Development. Your satisfaction with the project is my top priority! If you give me a chance to work with you More

Hi, this is a very interesting problem and I'm pretty sure I can solve it. I am a frequent projecteuler user, which is a site that provides this type of programming problems. I can definitely do this task in the most o More

I am a Python developer with 4+ years of experience that specializes in multi-platform applications using PyQt, PySide/PyQt,Scrapy, BeautifulSoup 4,,django, Pillow, Matplotlib, Xml, json, and csv modules, Celery I am More

Hello Sir/ Ma’am We are a group of Software Engineers (Programmers) having 10+ years of experience. Expert in JAVA, C, C++ , C# , Python, ANDROID,IOS, MATLAB, IONIC. Done 40+ projects here on FREELANCER.COM. More

Hi, Hope you are doing well! I would like to work on your project. I have excellent in skills with more than 6 Years experience. I'm sure that I will complete with high quality in the shortest time. I am always availa More

Hi, sir "SUCCESS = Faster Speed + Loyal Quality + High Credit" This is my slogan on working with client or employer I am an expert who have more 7 year's experience and have a powerful team. and we've ever devel More

I offer this cheap rate, since I am new to this website! Very experienced programmer offering good service.

Hello I have years of experience in Python programming. I can help in the code optimization and can complete the work with 100% satisfaction.

Dear Client I am an expert in python. I think I can do your task perfectly. If you want lower price and higher quality, please get touch with me. I will wait for your call. Thank you.....