| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem C
Bee Movie
Time Limit: 1000ms
Memory Limit: 65536kb Description
Barry B. Benson is "just an ordinary bee" in a hive located in Sheep's Meadow in Central Park in New York City. Barry recently graduated from college and is about to enter the hive's Honex Industries (a division of Honesco Corporation and owned by the Hexagon Group) honey-making workforce. Along with his best friend Adam Flayman (voiced by Matthew Broderick) Barry is initially very excited, but his latent, non-conformist attitude emerges upon finding out that his choice of job will never change once picked. He absolutely disappointed, he joins the team responsible for bringing the honey and pollination of the flowers to visit the world outside the hive. The bee will draw out in battle array when they want to go outside. Actually, this problem is about alignment of N (1 ≤ N ≤ 455) bees numbered 1..N who are grazing in their field that is about 15,000×15,000 units. Their grazing locations all fall on integer coordinates in a standard x,y scheme (coordinates are in the range 0..15,000). Barry looks up and notices that she is exactly lined up with Huacm534(bee) and AcmIcpc20060820322(bee). He wonders how many groups of three aligned bees exist within the field. Given the locations of all the bees (no two bees occupy the same location), figure out all sets of three bees are exactly collinear. Keep track of the sets, sorting the bees in each set by their ID number, lowest first. Then sort the sets by the three ID numbers (lowest first), breaking ties by examining the second and third ID numbers. Input
Line 1: A single integer, N Lines 2..N+1: Line i+1 describes bee i's location with two space-separated integers that are his x and y coordinates Output
Line 1: A single integer X that is the number of sets of three bees that are exactly collinear. A set of four collinear bees would, of course, result in four sets of three collinear bees. Lines 2..X+1: Each line contains three space-separated integers that are the bee ID numbers of three collinear bees. The lines are sorted as specified above. This output section is empty if no collinear sets exist. Sample Input
8 0 0 0 4 1 2 2 4 4 3 4 5 5 1 6 5 4 0 0 1 1 2 2 3 3 Sample Output
1 1 3 4 4 1 2 3 1 2 4 1 3 4 2 3 4 Hint
Be careful of floating point arithmetic. Floating point comparison for equality almost never works as well as one would hope. Explanation of the sample 1: Eight bees grazing on a grid whose lower left corner looks like this: . . . . 6 . 8 2 . 4 . . . . . . . . 5 . . . 3 . . . . . . . . . . 7 . 1 . . . . . . The digits mark the collinear bee IDs: . . . . * . * * . 4 . . . . . . . . * . . . 3 . . . . . . . . . . * . 1 . . . . . . Source
kenan5020@Monster
|