2014
03-06

# Circle and Triangle

LMY and YY are geometry lovers. They enjoy challenging each other with interesting geometry problems. One day, LMY puts a circle and a triangle on a plane. Then YY moves them. They find that the overlapping area of the circle and the triangle varies as the relative position between the two changes. LMY and YY want to find out the largest common area.

Input consists of one or more lines. For each line, there are four integers describing one test case: the lengths of three sides of a triangle a, b, c; and the radius of a circle r; where 1≤a≤b≤c≤100, 1≤r≤100, and a+b>c.

End of input is indicated by a line consisting four zeros.

Input consists of one or more lines. For each line, there are four integers describing one test case: the lengths of three sides of a triangle a, b, c; and the radius of a circle r; where 1≤a≤b≤c≤100, 1≤r≤100, and a+b>c.

End of input is indicated by a line consisting four zeros.

3 4 5 1
5 5 8 4
0 0 0 0

3.14
12.00

1. #include <cstdio>

int main() {
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。