首页 > ACM题库 > HDU-杭电 > HDU 4244-The Golden Ceiling[解题报告]HOJ
2015
05-23

HDU 4244-The Golden Ceiling[解题报告]HOJ

The Golden Ceiling

问题描述 :

The main office of the Bank of Zork was built in the Aragain Village(later known as Flatheadia)in the year 722 of the Great Underground Empire(GUE). In 788 GUE,the chairman, J.Pierpont Flathead, decided(shortly before his unexplained disappearance in 789), that it was time to completely redesign the already ornate bank atrium with a ceiling covered in brilliant gold leaf.

This new ceiling was not your ordinary ceiling. Although the atrium is essentially a big box,the ceiling would be slanted(supposedly,making the atrium look bigger). At the time,the exact dimensions of the rectangular atrium and the slope and location of the slanted ceiling had not been finalized. Flathead wanted to know how much gold leaf he would have to order from the Frobozz Magic Gold Leaf Company to cover the ceiling for different atrium dimensions and ceiling slants. He also wanted to allow the slanted part to possibly hit the floor of the box and/or the top of the box.

Maximum in the Cycle of 1

Consider the following rough sketches of some possibly atrium configurations:

Note: The dashed outline represents the original box,the horizontally ruled surface is the slanted part of the ceiling and the cross hatched surface is the part of the top of the box not cut off by the plane. The walls and floor of the atrium are transparent.The total area to be covered(the ceiling)is the slanted part plus any part of the top of the original box that is not cut off by the plane.

Your job is to write a program that Flathead could have used to calculate the amount gold leaf required to cover the ceiling for a particular configuration.
As a sad epilogue,the main branch was brought to ruins when the Curse of Megaboz befell it in 883GUE. Between the barbarian invasions of the 880′s and the countless looters that had tread the underground ruins in the year that followed, the entire bank with all its valuables, as well as its very expensive gold leaf ceiling, had been removed or vandalized. More information can be found on-line at:http://www.thezorklibrary.com/history/bank_of_zork.html.

输入:

The first line of input contains a single integer P,(1<=P<=1000),which is the number of data sets that follow. Each data set is a single line that contains the data set number,N,followed by a space, followed by seven space separated double precision floating point values,L,W,H,A,B,C and D. The values L,W and H specify the length, width and height of the atrium in Flathead Units(FU’s), respectively, and are always positive values. The values A,B,C and D specify the coefficients of the plane equation for the slanted part of the ceiling:

Ax + By + Cz = D

where :0 <= x <= L, 0 <= y <= W, 0 <= z <= H.

One corner of the original box is always at the origin (0,0,0)and the other at (L,W,H). The plane will never be vertical(C will be>=1.0)and the plane will always pass through the interior of the box (there will be points(x,y,z)in the box and strictly above the plane(Ax+By+Cz>D)).and others strictly below the plane (Ax+By+Cz<D).

输出:

The first line of input contains a single integer P,(1<=P<=1000),which is the number of data sets that follow. Each data set is a single line that contains the data set number,N,followed by a space, followed by seven space separated double precision floating point values,L,W,H,A,B,C and D. The values L,W and H specify the length, width and height of the atrium in Flathead Units(FU’s), respectively, and are always positive values. The values A,B,C and D specify the coefficients of the plane equation for the slanted part of the ceiling:

Ax + By + Cz = D

where :0 <= x <= L, 0 <= y <= W, 0 <= z <= H.

One corner of the original box is always at the origin (0,0,0)and the other at (L,W,H). The plane will never be vertical(C will be>=1.0)and the plane will always pass through the interior of the box (there will be points(x,y,z)in the box and strictly above the plane(Ax+By+Cz>D)).and others strictly below the plane (Ax+By+Cz<D).

样例输入:

3                                                     
1 10 12 15 -1.3 1 1.1 3.5                             
2 10 12 10 -1.3 1 1.1 11                              
3 13 9 10 -1.3 1 1.1 0

样例输出:

1 166 
2 164
3 144

/*BISMILLAHIRRAHMANIRRAHIM*/

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:0x800000")
//#define _CRT_SECURE_NO_WARNINGS 1

#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }

#define ALL(p) p.begin(),p.end()
#define MP(x, y) make_pair(x, y)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define SZ(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;

struct point {
    double x,y,z;
};

bool eql(point &a,point &b) {
	return fabs(a.x-b.x)<EPS && fabs(a.y-b.y)<EPS && fabs(a.z-b.z)<EPS;
}


double dist(point a,point b) {
	b.x-=a.x;
	b.y-=a.y;
	b.z-=a.z;
	return sqrt(sq(b.x)+sq(b.y)+sq(b.z));
}

double ar(point a,point b,point c) {
	double x=dist(a,b);
	double y=dist(b,c);
	double z=dist(c,a);
	double s=0.5*(x+y+z);
	return sqrt(s*(s-x)*(s-y)*(s-z));
}

int main() {
	//READ("in.txt");
	//WRITE("out.txt");
	int i,j,k,l,T,I,cn;
	double a,b,c,d,x,y,z;
	point tt[200];
	double g[3][2]={0};
	cin>>T;
	while(T--) {
	    cin>>I>>g[0][1]>>g[1][1]>>g[2][1]>>a>>b>>c>>d;
	    vector < pair < point , point > > r,tr;
	    for(i=0;i<2;i++) {
	        cn=0;
	        x=g[0][i];
	        for(j=0;j<2;j++) {
	            y=g[1][j];
	            z=(d-b*y-a*x)/c;
	            ////cout<<i<<' '<<j<<' '<<x<<' '<<y<<' '<<z<<'\n';
	            if(z>=0 && z<=g[2][1]) {
	                tt[cn].x=x;
	                tt[cn].y=y;
	                tt[cn].z=z;
	                cn++;
	            }
	        }

	        if(cn==2) {
	            r.PB(make_pair(tt[0],tt[1]));
	            continue;
	        }
	        for(j=0;j<2;j++) {
	            z=g[2][j];
	            y=(d-c*z-a*x)/b;
	            ////cout<<i<<' '<<j<<' '<<x<<' '<<y<<' '<<z<<'\n';
	            if(y>=0 && y<=g[1][1]) {
	                tt[cn].x=x;
	                tt[cn].y=y;
	                tt[cn].z=z;
	                cn++;
	            }
	        }
	        if(cn==2) r.PB(make_pair(tt[0],tt[1]));
	        else if(cn==3) {
				bool f=1;
				for(j=0;j<3 && f;j++) for(l=0;l<j && f;l++) if(!eql(tt[j],tt[l])) {
					r.PB(make_pair(tt[j],tt[l]));
					f=0;
				}
			}
	        //cout<<i<<' '<<cn<<' '<<r.size()<<'\n';
	        //cout<<r.back().first.x<<' '<<r.back().first.y<<' '<<r.back().first.z<<'\n';
	        //cout<<r.back().second.x<<' '<<r.back().second.y<<' '<<r.back().second.z<<'\n'<<'\n';
	    }
	    for(i=0;i<2;i++) {
	        cn=0;
	        y=g[1][i];
	        for(j=0;j<2;j++) {
	            x=g[0][j];
	            z=(d-b*y-a*x)/c;
	            if(z>=0 && z<=g[2][1]) {
	                tt[cn].x=x;
	                tt[cn].y=y;
	                tt[cn].z=z;
	                cn++;
	            }
	        }

	        if(cn==2) {
	            r.PB(make_pair(tt[0],tt[1]));
	            continue;
	        }
	        for(j=0;j<2;j++) {
	            z=g[2][j];
	            x=(d-c*z-b*y)/a;
	            if(x>=0 && x<=g[0][1]) {
	                tt[cn].x=x;
	                tt[cn].y=y;
	                tt[cn].z=z;
	                cn++;
	            }
	        }
	        if(cn==2) r.PB(make_pair(tt[0],tt[1]));
	        else if(cn==3) {
				bool f=1;
				for(j=0;j<3 && f;j++) for(l=0;l<j && f;l++) if(!eql(tt[j],tt[l])) {
					r.PB(make_pair(tt[j],tt[l]));
					f=0;
				}
			}
	    }
	    for(i=0;i<2;i++) {
	        cn=0;
	        z=g[2][i];
	        for(j=0;j<2;j++) {
	            y=g[1][j];
	            x=(d-b*y-c*z)/a;
	            if(x>=0 && x<=g[0][1]) {
	                tt[cn].x=x;
	                tt[cn].y=y;
	                tt[cn].z=z;
	                cn++;
	            }
	        }

	        if(cn==2) {
	            r.PB(make_pair(tt[0],tt[1]));
	            continue;
	        }
	        for(j=0;j<2;j++) {
	            x=g[0][j];
	            y=(d-c*z-a*x)/b;
	            if(y>=0 && y<=g[1][1]) {
	                tt[cn].x=x;
	                tt[cn].y=y;
	                tt[cn].z=z;
	                cn++;
	            }
	        }
	        if(cn==2) r.PB(make_pair(tt[0],tt[1]));
	        else if(cn==3) {
				bool f=1;
				for(j=0;j<3 && f;j++) for(l=0;l<j && f;l++) if(!eql(tt[j],tt[l])) {
					r.PB(make_pair(tt[j],tt[l]));
					f=0;
				}
			}
	    }
		for(i=0;i<r.size();i++) if(!eql(r[i].first,r[i].second)) tr.PB(r[i]);
		r=tr;
	    for(i=0;i<r.size();i++) {
	        //cout<<r[i].first.x<<' '<<r[i].first.y<<' '<<r[i].first.z<<'\n';
	        //cout<<r[i].second.x<<' '<<r[i].second.y<<' '<<r[i].second.z<<'\n'<<'\n';
	    }
		vector < point > ls;
		j=0;
		ls.push_back(r[0].first);
		j=0;
		for(i=0;i<r.size();i++) {
			for(k=0;k<r.size();k++) if(k!=j) {
				if(eql(ls.back(),r[k].first)) {
					ls.PB(r[k].second);
					break;
				}
				if(eql(ls.back(),r[k].second)) {
					ls.PB(r[k].first);
					break;
				}
			}
			j=k;
		}
		double res=0;
		for(i=0;i<ls.size();i++) //cout<<ls[i].x<<' '<<ls[i].y<<' '<<ls[i].z<<'\n';
		for(i=2;i<ls.size()-1;i++) res+=ar(ls[0],ls[i-1],ls[i]);
		z=g[2][1];
		if(fabs(r.back().first.z-z)<=EPS && fabs(r.back().second.z-z)<=EPS) {
			r.clear();
			r.PB(tr.back());
			//puts(":)");
			for(i=0;i<2;i++) {
				x=g[0][i];
				//cout<<(a*x+b*g[1][0]+c*z)<<' '<<a*x+b*g[1][1]+c*z<<'\n';
				if(a*x+b*g[1][0]+c*z<=d && a*x+b*g[1][1]+c*z<=d) {
					y=(d-c*z-a*x)/b;
					tt[0].x=x;
					tt[0].y=g[1][0];
					tt[0].z=z;
					tt[1].x=x;
					tt[1].y=g[1][1];
					tt[1].z=z;
					r.PB(make_pair(tt[0],tt[1]));
				}
				else if(a*x+b*g[1][0]+c*z<=d) {
					y=(d-c*z-a*x)/b;
					tt[0].x=x;
					tt[0].y=g[1][0];
					tt[0].z=z;
					tt[1].x=x;
					tt[1].y=y;
					tt[1].z=z;
					r.PB(make_pair(tt[0],tt[1]));
				}
				else if(a*x+b*g[1][1]+c*z<=d) {
					y=(d-c*z-a*x)/b;
					tt[0].x=x;
					tt[0].y=y;
					tt[0].z=z;
					tt[1].x=x;
					tt[1].y=g[1][1];
					tt[1].z=z;
					r.PB(make_pair(tt[0],tt[1]));
				}
			}
			for(i=0;i<2;i++) {
				y=g[1][i];
				if(a*g[0][0]+b*y+c*z<=d && a*g[0][1]+b*y+c*z<=d) {
					x=(d-c*z-b*y)/a;
					tt[0].x=g[0][0];
					tt[0].y=y;
					tt[0].z=z;
					tt[1].x=g[0][1];
					tt[1].y=y;
					tt[1].z=z;
					r.PB(make_pair(tt[0],tt[1]));
				}
				else if(a*g[0][0]+b*y+c*z<=d) {
					x=(d-c*z-b*y)/a;
					tt[0].x=g[0][0];
					tt[0].y=y;
					tt[0].z=z;
					tt[1].x=x;
					tt[1].y=y;
					tt[1].z=z;
					r.PB(make_pair(tt[0],tt[1]));
				}
				else if(a*g[0][1]+b*y+c*z<=d) {
					x=(d-c*z-b*y)/a;
					tt[0].x=x;
					tt[0].y=y;
					tt[0].z=z;
					tt[1].x=g[0][1];
					tt[1].y=y;
					tt[1].z=z;
					r.PB(make_pair(tt[0],tt[1]));
				}
				
			}
			tr.clear();
			for(i=0;i<r.size();i++) if(!eql(r[i].first,r[i].second)) tr.PB(r[i]);
			r=tr;
			for(i=0;i<r.size();i++) {
				//cout<<r[i].first.x<<' '<<r[i].first.y<<' '<<r[i].first.z<<'\n';
				//cout<<r[i].second.x<<' '<<r[i].second.y<<' '<<r[i].second.z<<'\n'<<'\n';
			}
			vector < point > ls;
			j=0;
			ls.push_back(r[0].first);
			j=0;
			for(i=0;i<r.size();i++) {
				for(k=0;k<r.size();k++) if(k!=j) {
					if(eql(ls.back(),r[k].first)) {
						ls.PB(r[k].second);
						break;
					}
					if(eql(ls.back(),r[k].second)) {
						ls.PB(r[k].first);
						break;
					}
				}
				j=k;
			}
			for(i=0;i<ls.size();i++) //cout<<ls[i].x<<' '<<ls[i].y<<' '<<ls[i].z<<'\n';
			for(i=2;i<ls.size()-1;i++) res+=ar(ls[0],ls[i-1],ls[i]);
		}
			
		cout<<I<<' '<<ceil(res-EPS)<<'\n';
	}

	return 0;
}