2013
12-21

# RedField

As the graph you see below, we named the red part "RedField".The read part is the intersection of an ellipse and a triangle.Now, 8600′s not good at math, so he wants you to help him calculate the area of the "RedField".

The first line of input contains n, the number of test cases. n lines follow.Each test case contains four numbers a, b, x, y(0 < b <= a <= x),and a is the lenth of OA, b is the lenth of OB,and x, y representing the coordinate of the point P.

For each test case, output the area of the "RedField",accurate up to 2 decimal places.

1
1.00 1.00 2.00 2.00

0.39

#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int i,j,flag,t;
double a,b,c,d,x,y,s;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
x=sqrt(1/(a*a*d*d+c*c*b*b))*a*c*b;
y=d*x/c;
s=(a*b/2)*acos(x/a);
printf("%.2f\n",s);

}
return 0;
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

2. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。