Completed

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

Skills: Python

See more: light box prev next buttons dont show, next previous light box, calculating area polygon python, online box drag drop javascript area, show next previous show light box, lightbox next button outside box, javascript selected show next box, python html next button, bounding box google maps latitude longitude, box bounding esp, macro calculate area bounding line excel, python hide task, python source code area polygon, task box pop, python crawler click next, python bounding volume, bounding box collision python, need 1000 words description for each of our two products pages

About the Employer:
( 1 review ) Prague, Czech Republic

Project ID: #20022379

Awarded to:

                                                    ducdac
                                                's Profile Picture"                                                    >
                                                </a>
                                            </figure>
                                        </div>
                                        <div class=
ducdac

I have read this project in detail. I am an expert in python. And I am sure I can do this project. I'll do my best to finish your project.

$20 USD in 1 day
(2 Reviews)
2.0

14 freelancers are bidding on average $32 for this job

roshanasim

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

$80 USD in 7 days
(29 Reviews)
5.0
alkajain2906

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

$25 USD in 1 day
(8 Reviews)
4.0
Panggumsok

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

$25 USD in 1 day
(3 Reviews)
4.4
drohanyadav

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

$50 USD in 3 days
(4 Reviews)
3.2
uzairnaseer920

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

$20 USD in 7 days
(5 Reviews)
2.5
Muhammadsamran

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

$10 USD in 1 day
(1 Review)
2.1
ninestar801

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

$90 USD in 7 days
(1 Review)
1.1
fivestarOne

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

$25 USD in 1 day
(0 Reviews)
0.0
vivi1990

Good day! I'm a licensed full stack programming developer and designer. I have many experiences in python image processing by using python openCV package. I have many experiences in c#,c++,c,java programming. I h More

$25 USD in 1 day
(0 Reviews)
0.0
stannor

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

$10 USD in 1 day
(0 Reviews)
0.0
ArnikaK

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

$25 USD in 2 days
(0 Reviews)
0.0
Akiano628

Hello! I have read your description of a project. I'm a full stack web developer. I want to let you know that I have great experience in web development. I can professionally work on your project. I'm interested in More

$20 USD in 3 days
(0 Reviews)
0.0
lzx0102

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.....

$25 USD in 1 day
(0 Reviews)
0.0