ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Championship 2000

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Cover an Arc

Time limit: 1.0 second
Memory limit: 64 MB
A huge dancing-hall was constructed for the Ural State University’s 80-th anniversary celebration. The size of the hall is 2000 × 2000 metres! The floor was made of square mirror plates with side equal to one metre. Then the walls were painted with an indelible paint. Unfortunately, in the end the painter flapped the brush and the beautiful mirror floor was stained with the paint. But not everything is lost yet! The stains can be covered with a carpet.
Nobody knows why, but the paint on the floor formed an arc of a circle (a centre of the circle lies inside the hall). The dean of the Department of Mathematics and Mechanics measured the coordinates of the arc's ends and of some other point of the arc (he is sure that this information is quite enough for any student of the Ural State University). The dean wants to cover the arc with a rectangular carpet. The sides of a carpet must go along the sides of the mirror plates (so, the corners of the carpet must have integer coordinates).
You should find the minimal area of such a carpet.


Input consists of six integers. The first two lines contain the coordinates of the arc's ends. The coordinates of an inner point of the arc follow them. Absolute values of all coordinates don't exceed 1000. The points don't belong the same straight line. The arc lies inside the square [−1000,1000]2.


Output the minimal area of the carpet covering this arc.


476 612
487 615
478 616
Problem Author: Alexander Mironenko
Problem Source: Ural State University Internal Contest October'2000 Students Session
To submit the solution for this problem go to the Problem set: 1043. Cover an Arc