2013
12-21

# Ellipse

Math is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth..
Look this sample picture:

A ellipses in the plane and center in point O. the L,R lines will be vertical through the X-axis. The problem is calculating the blue intersection area. But calculating the intersection area is dull, so I have turn to you, a talent of programmer. Your task is tell me the result of calculations.(defined PI=3.14159265 , The area of an ellipse A=PI*a*b )

Input may contain multiple test cases. The first line is a positive integer N, denoting the number of test cases below. One case One line. The line will consist of a pair of integers a and b, denoting the ellipse equation , A pair of integers l and r, mean the L is (l, 0) and R is (r, 0). (-a <= l <= r <= a).

For each case, output one line containing a float, the area of the intersection, accurate to three decimals after the decimal point.

2
2 1 -2 2
2 1 0 2

6.283
3.142

/*
hdu 1724 Ellipse simpson积分

simpson积分法 http://zh.wikipedia.org/zh-tw/%E8%BE%9B%E6%99%AE%E6%A3%AE%E7%A7%AF%E5%88%86%E6%B3%95
*/
#include<stdio.h>
#include<math.h>
const double eps=1e-8;
inline double jue(double a)
{
return a>0?a:-a;
}
int dbcmp(double a)
{
if(a>eps)return 1;
if(a<(-eps)) return -1;
return 0;
}
template<typename T>
inline T sqr(T d){return d*d;}
double a,b;
inline double func(double x)
{
return 2*b*sqrt(1-sqr(x)/sqr(a));
}
double simpson(double l,double r)
{
return (func(l)+func(r)+4*func((l+r)/2))/6*(r-l);
}
double work(double l,double r)
{
double mid=(l+r)/2;
double ans=simpson(l,r);
if(dbcmp(ans-simpson(l,mid)-simpson(mid,r))==0)
{
return ans;
}else
{
return work(l,mid)+work(mid,r);
}
}
int main()
{
int n;
double l,r;
scanf("%d",&n);
while(n--)
{
scanf("%lf%lf%lf%lf",&a,&b,&l,&r);
double ret=work(l,r);
printf("%.3f\n",ret);
}
return 0;
}

1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}