首页 > ACM题库 > HDU-杭电 > HDU 1724 Ellipse-计算几何-[解题报告] C++
2013
12-21

HDU 1724 Ellipse-计算几何-[解题报告] C++

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;
}

解题报告转自:http://blog.csdn.net/qq172108805/article/details/12177473


  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;
    }