АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1328. Ingress

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

A new energy source has been discovered on the Earth, dubbed exotic matter, or XM. Many points of XM concentration were discovered. Such points are called portals. A faction was found, called the Enlightened, whose intent is to use XM to help an alien civilization, the Shapers, obtain ingress to our world. They can link portals to each other with links. A link is a straight line segment with endpoints at two portals. The links must not intersect, or the black hole will grow upemerge and swallow the galaxy. So, if two portals are separated by a link they cannot be linked to each other. Every three portals linked to each other form a triangle called a control field. Control fields are an important part of the strategy aimed at setting control over the human civilization. All the people who are within a control field fall under control of the Enlightened. There is no relation between different control fields. A control field may share portals and links with another control field, or it may be located within another control field, or it may contain other control fields inside. There is another faction called the Resistance. Its members struggle against the intrusion of the Shapers.

They need your help in calculating the maximum number of control fields the Enlightened can make using a specified set of portals.

Limitations

3 ≤ n ≤ 10,000; –300,000 ≤ xi, yi ≤ 300,000

Input

The first line contains an integer n, the number of portals. Each of the following n lines contains two space-delimited integers x and y, the coordinates of the i-th portal.

Output

Write to the output file the maximum number of control fields that can be made.

Input

Output

Picture

4

0 0

2 0

2 2

0 2

2

Пример0

5

0 0

0 4

5 4

5 0

2 2

5

Пример1

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1327. C - Race Condition 1328. 1329. E - 4x4 1330. F - Sages 1331. G - Bus Conductor
 
время генерации 0.063 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.