3 seconds
256 megabytes
standard input
standard output
Kostya is a genial sculptor, he has an idea: to carve a marble sculpture in the shape of a sphere. Kostya has a friend Zahar who works at a career. Zahar knows about Kostya’s idea and wants to present him a rectangular parallelepiped of marble from which he can carve the sphere.
Zahar has n stones which are rectangular parallelepipeds. The edges sizes of the i-th of them are ai, bi and ci. He can take no more than two stones and present them to Kostya.
If Zahar takes two stones, he should glue them together on one of the faces in order to get a new piece of rectangular parallelepiped of marble. Thus, it is possible to glue a pair of stones together if and only if two faces on which they are glued together match as rectangles. In such gluing it is allowed to rotate and flip the stones in any way.
Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar.
The first line contains the integer n (1 ≤ n ≤ 105).
n lines follow, in the i-th of which there are three integers ai, bi and ci (1 ≤ ai, bi, ci ≤ 109) — the lengths of edges of the i-th stone. Note, that two stones may have exactly the same sizes, but they still will be considered two different stones.
In the first line print k (1 ≤ k ≤ 2) the number of stones which Zahar has chosen. In the second line print k distinct integers from 1 to n — the numbers of stones which Zahar needs to choose. Consider that stones are numbered from 1 to n in the order as they are given in the input data.
You can print the stones in arbitrary order. If there are several answers print any of them.
|
1 2 3 4 5 6 7 |
6 5 5 5 3 2 4 1 4 1 2 1 3 3 2 4 3 3 4 |
|
1 2 |
1 1 |
|
1 2 3 4 5 6 7 8 |
7 10 7 8 5 10 3 4 2 6 5 5 5 10 2 8 4 2 1 7 7 7 |
|
1 2 |
2 1 5 |
In the first example we can connect the pairs of stones:
- 2 and 4, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1
- 2 and 5, the size of the parallelepiped: 3 × 2 × 8 or 6 × 2 × 4 or 3 × 4 × 4, the radius of the inscribed sphere 1, or 1, or 1.5respectively.
- 2 and 6, the size of the parallelepiped: 3 × 5 × 4, the radius of the inscribed sphere 1.5
- 4 and 5, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1
- 5 and 6, the size of the parallelepiped: 3 × 4 × 5, the radius of the inscribed sphere 1.5
Or take only one stone:
- 1 the size of the parallelepiped: 5 × 5 × 5, the radius of the inscribed sphere 2.5
- 2 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1
- 3 the size of the parallelepiped: 1 × 4 × 1, the radius of the inscribed sphere 0.5
- 4 the size of the parallelepiped: 2 × 1 × 3, the radius of the inscribed sphere 0.5
- 5 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1
- 6 the size of the parallelepiped: 3 × 3 × 4, the radius of the inscribed sphere 1.5
It is most profitable to take only the first stone.
题意
给n个立方体，告知每个长方体的三条边长，现在可以选出其中一个长方体或者其中两个长方体拼成的一个长方体，然后使所选长方体包含的球体积最大，球的体积只跟长方体的最短边有关，所以问题也就转化成如何使得长方体的最小边最大。
思路
输入的时候，将三条边排序过后存储（注意还要存储长方体的原始索引），然后对所有的长方体进行递减排序，排序的时候最后比较最小边，因为两个长方体只有最小边不同，另外两条边相同的前提下拼接而成的新长方体最小边才会大于等于原始最小边（等于的话是因为可能只有一条最大边），对所有的长方体排完序过后，能拼成一个长方体的两个长方体都是相邻的，所以可以在\(\textit{O(n)}\)时间内找到最佳选择。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
/* * File Name: 733D.cpp * Author: razrLeLe * Mail: razrlele@gmail.com */ #include <bits/stdc++.h> #define ll long long using namespace std; #define INF 0x3f3f3f3f #define LOCAL struct R{ ll e[3]; int id; }; bool customG ( R a, R b){ if( a.e[1] == b.e[1]) { if( a.e[2] == b.e[2]) return a.e[0] > b.e[0]; return a.e[2] > b.e[2]; } return a.e[1] > b.e[1]; } int main(int argc, char ** argv) { #ifdef LOCAL freopen("/Users/yuyue/build/data.txt", "r", stdin); // freopen("/Users/yuyue/build/out.txt", "w", stdout); #endif const int maxn = 100007; vector< R > rp; int n; while( cin >> n) { ll max_ans = 0; int max_i = -1, max_j = -1; int ans_num = 1; for(int i = 0; i < n; i++) { R tmp; cin >> tmp.e[0] >> tmp.e[1] >> tmp.e[2]; tmp.id = i+1; sort(tmp.e, tmp.e+3); rp.push_back(tmp); } sort(rp.begin(), rp.end(), customG); for(int i = 0 ; i < n; ++i) { if( max_ans < rp[i].e[0]) { max_ans = rp[i].e[0]; ans_num = 1; max_i = rp[i].id; } if( i < n-1) { if( rp[i].e[1] == rp[i+1].e[1] && rp[i].e[2] == rp[i+1].e[2]) { ll newmin = rp[i].e[0] + rp[i+1].e[0]; newmin = min(newmin, min(rp[i].e[2], rp[i].e[1])); if(newmin > max_ans) { max_ans = newmin; max_i = rp[i].id; max_j = rp[i+1].id; ans_num = 2; } } } } if( ans_num == 2) { cout << ans_num << endl; cout << max_i << " " << max_j << endl; } else cout << ans_num << endl << max_i << endl; } return 0; } |