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
|
|
|
5
0 0
0 4
5 4
5 0
2 2
|
5
|
|
