Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |

## HOUSES2 - Houses |

You are given three triangle houses. Each house is presented by three points in the 2D coordination. Houses are not overlap but can share points on their border.

You stay at point (sx, sy) and want to reach (ex, ey) by a shortest path. Your path can not intersect with a house but you can go a long a house’s border. However, you can not “go through” the walls as follow (just an example, please use natural meaning):

You are to write a program to print the length of the shortest path.

Input

The input begins with T – number of test cases. For each test case:

• The first line of each test case consists of sx, sy, ex, ey.

• In next three lines, each line consists of 6 numbers x1, y1, x2, y2, x3, y3 denote

coordinates of a house.

Output

For each test case, print the length of the shortest path with exactly 5 precision digits.

Limits

T <= 20

The absolute values of coordinates are less than 1000.

Sample input

1

0 0 3 0

1 0 2 0 1 1

2 0 2 -1 3 -1

2 1 3 1 2 2

Sample output

3.65028

Được gửi lên bởi: | sieunhan |

Ngày: | 2009-11-29 |

Thời gian chạy: | 1s-1.996s |

Giới hạn mã nguồn: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET |

Nguồn bài: | Khuc Anh Tuan - ACM Vietnam Practice |