首页 > ACM题库 > HDU-杭电 > Hdu 1417 Gleaming the Cubes-计算几何[解题报告] C++
2013
12-10

Hdu 1417 Gleaming the Cubes-计算几何[解题报告] C++

Gleaming the Cubes

问题描述 :

As chief engineer of the Starship Interprize, the task of repairing the hyperstellar, cubic, transwarped-out software has fallen on your shoulders. Simply put, you must compute the volume of the intersection of anywhere from 2 to 1000 cubes.

输入:

The input data file consists of several sets of cubes for which the volume of their intersections must be computed. The first line of the data file contains a number (from 2 to 1000) which indicates the number of cubes which follow, one cube per line. Each line which describes a cube contains four integers. The first three integers are the x, y, and z coordinates of the corner of a cube, and the fourth integer is the positive distance which the cube extends in each of the three directions (parallel to the x, y, and z axes) from that corner.

输出:

Following the data for the first set of cubes will be a number which indicates how many cubes are in a second set, followed by the cube descriptions for the second set, again one per line. Following this will be a third set, and so on. Your program should continue to process sets of cubes, outputting the volume of their intersections to the output file, one set per line, until a zero is read for the number of cubes.Note that the data file will always contain at least one set of cubes, and every set will contain at least 2 and at most 1000 cubes. For any given set of cubes, the volume of their intersections will not exceed 1,000,000 units.

样例输入:

2
0 0 0 10
9 1 1 5
3
0 0 0 10
9 1 1 5
8 2 2 3
0

样例输出:

25
9

让我们发现长方体的形成多个多维数据集的交集的体积。

#include<iostream>
#include<vector>
using namespace std;
bool intersect( pair<int,int> a, pair<int,int> b, pair<int,int> &ret ){
  ret.first = max(a.first, b.first);
  ret.second = min(a.second, b.second);
  if( ret.second <= ret.first ) return false;
  else return true;
}
int main(){
  while(true){
    vector< pair<int, int> > xv, yv, zv;
    int n;
    cin >> n;
    if( n == 0 ) break;
    int intersected_x, intersected_y, intersected_z;
    for(int i = 0; i < n; ++i){
      int x, y, z, d;
      cin >> x >> y >> z >> d;
      xv.push_back( make_pair( x, x+d ) );
      yv.push_back( make_pair( y, y+d ) );
      zv.push_back( make_pair( z, z+d ) );
    }
    intersected_x = xv[0].second - xv[0].first;
    intersected_y = yv[0].second - yv[0].first;
    intersected_z = zv[0].second - zv[0].first;

    if( n > 1 ){
      pair<int,int> xintersect, yintersect, zintersect;

      if( !intersect( xv[0], xv[1], xintersect ) )
	intersected_x = 0;
      else
	intersected_x = xintersect.second - xintersect.first;
      for(unsigned int i = 2; i < n; ++i){
	if( !intersect( xintersect, xv[i], xintersect ) ){
	  intersected_x = 0;
	  break;
	}
	intersected_x = xintersect.second - xintersect.first;
      }

      if( !intersect( yv[0], yv[1], yintersect ) )
	intersected_y = 0;
      else
	intersected_y = yintersect.second - yintersect.first;
      for(unsigned int i = 2; i < n; ++i){
	if( !intersect( yintersect, yv[i], yintersect ) ){
	  intersected_y = 0;
	  break;
	}
	intersected_y = yintersect.second - yintersect.first;
      }

      if( !intersect( zv[0], zv[1], zintersect ) )
	intersected_z = 0;
      else
	intersected_z = zintersect.second - zintersect.first;
      for(unsigned int i = 2; i < n; ++i){
	if( !intersect( zintersect, zv[i], zintersect ) ){
	  intersected_z = 0;
	  break;
	}
	intersected_z = zintersect.second - zintersect.first;
      }
    }

    //cout << intersected_x << " " << intersected_y << " " << intersected_z << endl;

    cout << intersected_x * intersected_y * intersected_z << endl;
  }
  return 0;
}

 


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……