2011/05/12 - by
Oneplus
• ACM Group
• HCPC 2011 Spring
HCPC 2011 Spring Online Contest 解题报告
这篇本该是校赛之后就放出来的解题报告终于被我拖啊拖啊拖到了现在，大家拍死我吧。
_________________________我是被拍死的分割线_________________________
比赛前收到了16道题，其中有一道数据范围描述不好，而且标程做法也不是很科学，所以就bang掉。后来又害怕没有水题做，我就独断，祭出了上次校赛因为水过头而被bang掉的Default Password。整体评价一下难度（sevenzero版）
| Pid | Title | Author | Category | Expected Difficulty(5) |
|---|---|---|---|---|
| A | RPNF | yangjing | 表达式求值 | 1 |
| B | Default Password | Unknown | 水 | 0 |
| C | Censorship | sevenzero | 字符串、DP | 2.5 |
| D | The Final Battle of Daydream | jerrybond | 智力题 | 1.5 |
| E | Costume Party | chenyuanqin | 暴搜，数学 | 3 |
| F | Go Home | icek | 最短路 | 2.5 |
| G | Alex's Problem | 胡越 | 几何、胡越题 | 4 |
| H | Zhou Yi II | sevenzero | 水 | 0 |
实际结果是70学长对于自己的题目难度估计不足，比赛中只有4次通过。而icek的最短路由于比较赤裸，被大家纷纷ac。所以感觉Go Home打2分，Censorship打3分比较合适。当然这是事后诸葛了。阿沁的搜索其实难度不大，数据也不是很硬，但是比赛时还是卡了一批人。完全可以水一水吗~
_________________________我是被拍死的分割线_________________________
RPNF
基本的表达式求值，中缀转后缀。按照yangjing学长的说法，两个栈就可以搞定的题。不过描述上略有瑕疵，没有提到a-b-c的情况。在算符优先级的表述上也有一定的混淆。还有，据羊说，用scanf会出错，gets过，不知道数据中是不是有空格，没有深入辨证。
具体算法是维护两个栈，一个放操作数，一个放操作符。判断扫描到的字符。如果是左括号，直接放入操作符栈，如果是右括号，就一直弹栈到遇到左括号，如果是操作数，直接放入操作数栈。如果是操作符，要判断栈顶和扫描字符的优先级，后者高则把后者放到操作数栈，否则一直弹栈到后者高于前者。
#include <iostream>
#include <cstring>
#include <cmath>
#define PRINT(x) cout <<(#x)<<" "<<x<<endl;
using namespace std;
const int SIZE = 512;
int legal(char ch){
if(ch == ')') return 4;
if(ch == '(') return 3;
if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^') return 2;
if(ch >= 'a' && ch <= 'z') return 1;
return 0;
}
int pri(char ch){
if(ch == '+') return 1;
if(ch == '-') return 2;
if(ch == '*') return 3;
if(ch == '/') return 4;
if(ch == '^') return 5;
return 0;
}
int main() {
char op[SIZE],opn[SIZE], ch;
int cas, opTop, opnTop;
scanf( "%d", &cas );
getchar();
while(cas--) {
string buf;
getline( cin, buf ); //PRINT(buf);
int kind; opTop = -1; opnTop = -1;
for(int i = 0; i < buf.size(); i ++) {
//PRINT(buf[i]);
if((kind = legal(buf[i])) == 0) continue;
else {
if(kind == 4) { while(op[opTop] != '(') opn[++ opnTop] = op[opTop --]; --opTop; }
else if(kind == 3) { op[++ opTop] = buf[i]; }
else if(kind == 2) {
if(pri(buf[i])>pri(op[opTop])) op[++ opTop] = buf[i];
else { while(pri(buf[i])<=(pri(op[opTop]))) opn[++ opnTop] = op[opTop --]; op[++ opTop] = buf[i];}}
else opn[++ opnTop] = buf[i];
}
//PRINT(opTop); PRINT(opnTop); PRINT(i);
}
//PRINT(opnTop);
for(int i = 0; i <= opnTop; i ++ ) putchar(opn[i]);
for(int i = opTop; i >= 0; i --) putchar(op[i]); putchar('\n');
}
return 0;
}
Default Password
判断输入字符串是不是”wujiawei”…
Censorship
这个等70学长补一个解题报告吧。
[05.20更新] 预处理先将不同的单词向整数做一个映射，可以用map实现，这样单词都被整数替代了，操作起来会方便很多。
用dp[i][j]表示sensitive information的前j个单词组成的子列在internet information的前i个单词组成的子序列中出现的次数。
转移方程是dp[i][j]=dp[i-1][j-1]+dp[i-1][j] (internet information的第i个单词和sensitive information的第j个单词相同) 和 dp[i][j]=dp[i-1][j] (internet information的第i个单词和sensitive information的第j个单词不同)。
加上negative单词情况后，就先将negative单词从从sensitive information中除去，如果它前面是第i个单词就在一个数组neg中把neg[i]标记为negative单词。再加一个转移方程dp[i][j]=0 (neg[j]与internet information的第i个单词相同)，即出现了internet information中出现了negative单词，sensitive information的前j个单词组成的所有子序列不可能最后转移到dp[n][m]，故将dp[i][j]置0。最后dp[n][m]为答案，n是internet information中单词数，m是sensitive information中非负单词数。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define ALL(c) (c).begin(),(c).end()
#define FIL(c,n) memset(c,n,sizeof(c))
#define L 100001
#define N 22
#define W 33
#define MOD 10007
int dp[L][N];
map<string,int> mp;
int ins(string s)
{
int n=mp.size();
if(mp.count(s))
return mp[s];
else
return mp[s]=n;
}
bool isc(char c)
{
if(c>='A'&&c<='Z') return 1;
if(c>='a'&&c<='z') return 1;
return 0;
}
int main()
{
//freopen("censorship.in","r",stdin);
//freopen("censorship.out","w",stdout);
int cas;
scanf("%d",&cas);
for(int ct=0;ct<cas;ct++)
{
mp.clear();
int n;
scanf("%d",&n);
char seq[N][W];
char s[L];
int word[L];
int cnt=0,neg[N],pos[N];
FIL(neg,-1);
FIL(pos,-1);
for(int i=0;i<n;i++)
{
scanf("%s",seq[i]);
if(seq[i][0]=='!')
neg[cnt]=ins(string(seq[i]+1));
else
pos[++cnt]=ins(string(seq[i]));
}
gets(s);
gets(s);
int cw=0;
for(int i=0;s[i];i++)
{
if(isc(s[i]))
{
string ts;
int j;
for(j=i;isc(s[j]);j++)
ts+=s[j];
i=j-1;
word[++cw]=ins(ts);
continue;
}
}
FIL(dp,0);
dp[0][0]=1;
for(int i=1;i<=cw;i++)
for(int j=0;j<=cnt;j++)
{
if(j&&pos[j]==word[i])
dp[i][j]=(dp[i-1][j-1]+dp[i][j])%MOD;
dp[i][j]=(dp[i-1][j]+dp[i][j])%MOD;
if(neg[j]==word[i])
dp[i][j]=0;
}
printf("%d\n",dp[cw][cnt]);
}
return 0;
}
The Final Battle of Daydream
[By jerrybond]本题很容易想到的解法是，申请一个大小为300,000的布尔数组，用来标记哪些数字出现过，哪些没有，这样很容易就能找到丢失的两个数字了。时间复杂度O(n)，空间复杂度也是O(n)。但遗憾的是，在1024K 的内存限制下，这种做法是行不通的。
仔细观察题目，也许你不禁会问：为什么只有两个士兵丢失，而不是1000或10000 个呢？事实上，我们只需要知道这两个数字的和与积，就可以通过解二元方程组得到要找的两个数字，而无需消耗过多的内存。 设丢失的两个士兵的编号为a、b，那么
- a+b=sum(i)-sum(left)
- a2+b2=sum(i2)-sum(left2)
剩下的就是解一元二次方程的事情了。
#include <cstdio>
#include <cstring>
#include <cmath>
#define sqr(x) ((x)*(x))
#define PRINT(x) cout <<(#x)<<" "<<x<<endl;
using namespace std;
int main() {
double n;
while(scanf("%lf",&n)==1){
double N = 0.0, M = 0.0;
for(double i = 1; i <= n; i ++ ) {
N = N + i;
M = M + sqr(i);
}
for(int i = 2; i < n; i ++) {
double x; scanf( "%lf", &x );
N = N - x; M = M - sqr(x);
}
double delta = sqrt(2.0 * M - sqr(N));
//printf( "TEST %.10lf %.10lf %.10lf\n", N, M, delta);
double x = 0.5 * (N - delta), y = 0.5 * (N + delta);
printf( "%.0lf %.0lf\n", x, y );
}
return 0;
}
Costume Party
[By chenyuanqin]很明显，可以抽象成一个图论模型：每个女生当成一个点，所有认识的人之间连接一条边。每一种服装就是一种颜色。那么，就是用m种颜色给这个图点染色，每条边的两个顶点颜色不能一样，计算染色方案。
- 完全图k的用m种颜色方案数 f（k，m）= m * （m-1）*。。。（m-k+1） 完全图，两两之间有边，不能有任何两个点颜色一样。
- 普通的图G对于不存在的边（u，v）。 f（G）= f（G + (u，v)）+ f（G/(u，v)）对于G的所有染色方案，u，v要么颜色不一样，那么它在f（G+(u，v)）中。如果u，v颜色一样，那么它在f（G/(u，v)）中，G/(u，v)为点收缩操作，即将u，v糅合成一个点w，它关联所有u，v关联的顶点。
不断进行2操作，那么G将会变成一个个的完全图，然后分别用1来计算即可。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <fstream>
using namespace std;
#define mod 9999997
int n, m, k ;
bool adj[ 11 ][ 11 ];
bool del[ 11 ];
int a[ 100001 ][ 11 ];
void find_not( int* a, int* b )
{
for ( int i = 1; i <= n; i++ )
if ( !del[ i ] )
for ( int j = 1; j <= n; j++ )
{
if ( !del[ j ] && !adj[ i ][ j ] && i != j )
{
*a = i, *b = j;
return;
}
}
*a = -1;
}
int getNum( int t )
{
int res = 1;
//printf( "t %d\n", t );
if ( t > m ) return 0;
return a[ m ][ t ];
}
//int ttt = 0;
int dfs( int u, int v, int num )
{
int res = 0, a, b;
// ttt++;
// if ( ttt % 10000 == 0 )
// printf( "%d\n", ttt );
bool temp[ 101 ];
adj[ v ][ u ] = adj[ u ][ v ] = true;
find_not( &a, &b );
res += ( a == -1 ? getNum( num ) : dfs( a, b, num ) );
adj[ v ][ u ] = adj[ u ][ v ] = false;
del[ v ] = true;
for ( int i = 1; i <= n; i++ )
temp[ i ] = adj[ u ][ i ];
for ( int i = 1; i <= n; i++ )
adj[ i ][ u ] = adj[ u ][ i ] = adj[ u ][ i ] | adj[ v ][ i ];
find_not( &a, &b );
res += ( a == -1 ? getNum( num - 1 ) : dfs( a, b, num - 1 ) );
del[ v ] = false;
for ( int i = 1; i <= n; i++ )
adj[ i ][ u ] = adj[ u ][ i ] = temp[ i ];
return res % mod;
}
int solve()
{
int u, v;
find_not( &u, &v );
if ( u == -1 )
return getNum( n );
return dfs( u, v, n );
}
int cas;
int main()
{
freopen( "costume.in", "r", stdin );
freopen( "costume.out", "w", stdout );
for ( int i = 1; i < 100001; i++ )
{
a[ i ][ 0 ] = 1;
int temp = min( i, 10 );
for ( int j = 1; j <= temp; j++ )
{
a[ i ][ j ] = ( 1LL * a[ i ][ j - 1 ] * 1LL * ( i - j + 1 ) ) % mod;
}
}
while ( scanf( "%d %d %d", &m, &n, &k ) == 3 )
{
int a, b;
memset( adj, 0, sizeof( adj ) );
memset( del, 0, sizeof( del ) );
for ( int i = 1; i <= k; i++ )
{
scanf( "%d %d", &a, &b );
adj[ a ][ b ] = adj[ b ][ a ] = true;
}
printf( "Case #%d\n", ++cas );
printf( "%d\n", solve() );
}
return 0;
}
短小暴力赤裸版见下。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define sz(x) ((int)(x).size())
using namespace std;
const int N = 16, MOD = 9999997;
typedef long long LL;
int G[N][N], res[N], clr[N]; LL C[100001][11];
int m, n, k;
void dfs(int now, int kind) {
if(now == n){
res[kind] ++;
return;
}
for(int i = 1; i <= kind; i ++ ) {
clr[now] = i; bool flag = true;
for(int j = 0; j < n; j ++) if(G[now][j] && clr[now] == clr[j]) {flag = false; break;}
if(flag) dfs(now+1,kind);
clr[now] = 0;
}
clr[now] = kind+1;
dfs(now+1,kind+1);
clr[now] = 0;
}
void init(){
for(int i=1; i<=100000; i++)
C[i][1]=(LL)i;
for(int i=2; i<=100000; i++){
for(int j=2; j<=min(i,10); j++) {
C[i][j] = (C[i-1][j-1]+C[i-1][j])%MOD;}
}
}
int main(){
int cas = 0;
init();
while(scanf("%d%d%d", &m, &n, &k) == 3){
memset(G, 0, sizeof(G));
memset(res,0,sizeof(res));
for(int i = 0; i < k; i++) {
int u, v;
scanf( "%d%d", &u, &v ); u --; v --;
G[u][v] = G[v][u] = 1;
}
int kind = 0; dfs(0, kind);
LL ans = 0L; LL pw = 1L;
for(int i = 1; i <= n; i ++) {
pw = (pw * (LL)i)%MOD;
//cout << pw << endl;
ans = ((ans+((C[m][i]*res[i]) % MOD) * pw) % MOD) % MOD;
}
cout << "Case #" << ++ cas << endl;cout << ans << endl;
}
return 0;
}
Go Home
[By icek]此题本意是考察堆优化dijkstra变形，事实上用动态规划，拆点最短路什么的都可以做。
解决问题的核心是用数组dis[i][j]记录在走到点i并且花费为j的情况下所需要的最小时间，即将原来dijkstra算法中记录最小状态的一维数组改成两维来表示。
因为堆优化dijkstra中以时间最小来维护堆，所以当要对终点做拓展的时候直接退出，就可以保证所用时间最小，输出最小值即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 505;
const int INF = 0x3fffffff;
int first[N];
int cnt = 1;
struct edge
{
int u, v, c, t, next;
} g[N * 4];
void add(int u, int v, int c, int t)
{
g[cnt].u = u;
g[cnt].v = v;
g[cnt].c = c;
g[cnt].t = t;
g[cnt].next = first[u];
first[u] = cnt++;
}
struct node
{
int w, u, t;
bool operator < ( const node &a ) const
{
return t > a.t;
}
};
int n, m, C;
int dis[N][N];
bool used[N][N];
node queue[N * N];
bool relax(int u, int w, int v, int c, int t)
{
if (dis[u][w] + t < dis[v][w + c])
{
dis[v][w + c] = dis[u][w] + t;
return true;
}
return false;
}
void dij(int u)
{
for (int i = 0; i <= n; ++i) for (int j = 0; j <= C; ++j) dis[i][j] = INF;
memset(used, false, sizeof(used));
int tail = 0;
int v, w, c, t;
dis[u][0] = 0;
queue[tail].u = u;
queue[tail].w = 0;
queue[tail].t = 0;
tail++;
make_heap(queue, queue + tail);
while (tail > 0)
{
pop_heap(queue, queue + tail);
tail--;
u = queue[tail].u;
if ( u == n ) break;
w = queue[tail].w;
if ( !used[u][w] )
{
used[u][w] = true;
for (int tmp = first[u]; tmp ; tmp = g[tmp].next)
{
v = g[tmp].v;
c = g[tmp].c;
t = g[tmp].t;
if ( w + c <= C && !used[v][w + c] && relax(u, w, v, c, t) )
{
queue[tail].u = v;
queue[tail].w = w + c;
queue[tail].t = dis[v][w + c];
tail++;
push_heap(queue, queue + tail);
}
}
}
}
return;
}
int main()
{
int cases, u, v, c, t;
scanf("%d", &cases);
while (cases--)
{
memset(first, 0, sizeof(first));
cnt = 1;
scanf("%d %d %d", &n, &m, &C); // n:1~n
for (int i = 0; i < m; ++i)
{
scanf("%d %d %d %d", &u, &v, &c, &t);
add(u, v, c, t);
add(v, u, c, t);
}
dij(1);
int ans = INF;
for (int i = C; i >= 0; --i)
{
if (dis[n][i] != INF)
{
ans = min(ans, dis[n][i]);
}
}
printf("%d\n", ans == INF ? -1 : ans);
}
return 0;
}
这个题我是用搜索做的，写了一个短小版，见下。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define sz(x) ((int)(x).size())
using namespace std;
const int NN = 505, CC = 505;
struct node {
int v, w, c;
node() {}
node(int _v, int _w, int _c):v(_v),w(_w),c(_c) {}
};
struct state {
int v, w, c;
state() {}
state(int _v, int _w, int _c):v(_v),w(_w),c(_c) {}
bool operator < (const state& t) const {
if(w != t.w) return w > t.w; return v > t.v; }
};
vector<node> g[NN];
priority_queue <state> pq;
int vst[NN][CC];
int main() {
int cas;
scanf( "%d", &cas );
while(cas --) {
int N, M, C;
scanf("%d%d%d", &N, &M, &C);
memset(vst,0,sizeof(vst));
for(int i = 0; i < N; i ++ ) g[i].clear();
while(pq.empty() == false) pq.pop();
for(int i = 0; i < M; i ++ ) {
int u, v, c, w;
scanf("%d%d%d%d", &u, &v, &c, &w); u--; v--;
g[u].push_back(node(v,w,c));
g[v].push_back(node(u,w,c));
}
pq.push(state(0,0,0));
int ans = -1;
while(pq.empty() == false) {
state now = pq.top(); pq.pop();
int v = now.v, c = now.c, w = now.w;
if(vst[v][c] == true) continue;
if(v == N - 1) { ans = w; break; }
vst[v][c] = true;
for(int i = 0; i < sz(g[v]); i ++ ){
int vv = g[v][i].v, ww = g[v][i].w + w, cc = g[v][i].c + c;
if(cc > C) continue;
pq.push(state(vv, ww, cc));
}
}
cout << ans << endl;
}
return 0;
}
#### Alex’s Problem
[By Alex]根据所给的三个点确定平面，然后求出此平面与正方体的12条棱的交点（平行的不算），保留坐标三个值均在[-100,100]的交点，去掉重复的后就得到了需要求面积的多边形的全部顶点。此时可以根据顶点个数和位置判断界面类型，截面可能是三角形，平行四边形，梯形，五边形和六边形，然后再去算面积。这里还有一种更为简单的方法，需要用到以下定理：
空间多边形 (A1,A2…An)的各顶点坐标为Ai(xi,yi,zi) (i = 1,2,…,n), 则它的面积为
其中
我们已经得到了所有的顶点，只需要把它们按多边形顺序顺时针或逆时针排序，而这件事也是很简单的，因为对于任何一个点，它的下一个点是跟它共面的。排好后按照上面的公式很容易就能求出面积了。
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <set>
#include <iomanip>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
using namespace std;
struct point3 {
double x, y, z;
point3(double a = 0, double b = 0, double c = 0) {
x = a, y = b, z = c;
}
bool operator<(const point3 p) const {
if (fabs(p.x - x) > eps)
return x < p.x;
if (fabs(p.y - y) > eps)
return y < p.y;
if (fabs(p.z - z) > eps)
return z < p.z;
return false;
}
bool operator==(const point3 p) const {
return fabs(p.x - x) < eps && fabs(p.y - y) < eps && fabs(p.z - z) < eps;
}
};
struct line3 {
point3 a, b;
line3(point3 a0, point3 b0) {
a = a0;
b = b0;
}
line3() {
}
};
struct plane3 {
point3 a, b, c;
plane3(point3 a0, point3 b0, point3 c0) {
a = a0;
b = b0;
c = c0;
}
plane3() {
}
};
line3 make_line(point3 a, point3 b) {
line3 p(a, b);
return p;
}
double dmult(point3 u, point3 v) {
return u.x * v.x + u.y * v.y + u.z * v.z;
}
point3 xmult(point3 u, point3 v) {
point3 ret;
ret.x = u.y * v.z - v.y * u.z;
ret.y = u.z * v.x - u.x * v.z;
ret.z = u.x * v.y - u.y * v.x;
return ret;
}
point3 subt(point3 u, point3 v) {
point3 ret;
ret.x = u.x - v.x;
ret.y = u.y - v.y;
ret.z = u.z - v.z;
return ret;
}
point3 pvec(plane3 s) {
return xmult(subt(s.a, s.b), subt(s.b, s.c));
}
bool parallel(line3 l, plane3 s) {
return zero(dmult(subt(l.a, l.b), pvec(s)));
}
point3 intersection(line3 l, plane3 s) {
point3 ret = pvec(s);
double t = (ret.x * (s.a.x - l.a.x) + ret.y * (s.a.y - l.a.y) + ret.z * (s.a.z - l.a.z)) /
(ret.x * (l.b.x - l.a.x) + ret.y * (l.b.y - l.a.y) + ret.z * (l.b.z - l.a.z));
ret.x = l.a.x + (l.b.x - l.a.x) * t;
ret.y = l.a.y + (l.b.y - l.a.y) * t;
ret.z = l.a.z + (l.b.z - l.a.z) * t;
return ret;
}
line3 edge[15];
int main() {
point3 p1(100, 100, 100);
point3 p2(-100, 100, 100);
point3 p3(100, -100, 100);
point3 p4(100, 100, -100);
point3 p5(-100, -100, 100);
point3 p6(-100, 100, -100);
point3 p7(100, -100, -100);
point3 p8(-100, -100, -100);
edge[0] = make_line(p1, p2);
edge[1] = make_line(p1, p3);
edge[2] = make_line(p1, p4);
edge[3] = make_line(p2, p5);
edge[4] = make_line(p2, p6);
edge[5] = make_line(p3, p5);
edge[6] = make_line(p3, p7);
edge[7] = make_line(p4, p6);
edge[8] = make_line(p4, p7);
edge[9] = make_line(p5, p8);
edge[10] = make_line(p6, p8);
edge[11] = make_line(p7, p8);
point3 p[5];
while (scanf("%lf%lf%lf", &p[0].x, &p[0].y, &p[0].z) == 3) {
scanf("%lf%lf%lf", &p[1].x, &p[1].y, &p[1].z);
scanf("%lf%lf%lf", &p[2].x, &p[2].y, &p[2].z);
plane3 P(p[0], p[1], p[2]);
set<point3> s;
for (int i = 0; i < 12; i++) {
if (!parallel(edge[i], P)) {
point3 tmp = intersection(edge[i], P);
if (tmp.x - 100 < eps && tmp.y - 100 < eps && tmp.z - 100 < eps
&& tmp.x + 100 > -eps && tmp.y + 100 > -eps && tmp.z + 100 > -eps)
s.insert(tmp);
}
}
int n = s.size();
point3 list[10];
set<point3>::iterator p1;
for (int i = 0; i < n; i++) {
if (i == 0) {
list[i] = *(s.begin());
s.erase(s.begin());
continue;
}
for (p1 = s.begin(); p1 != s.end(); p1++) {
if ((fabs(list[i - 1].x - (*p1).x) < eps && (fabs(list[i - 1].x - 100) < eps || fabs(list[i - 1].x + 100) < eps))
|| (fabs(list[i - 1].y - (*p1).y) < eps && (fabs(list[i - 1].y - 100) < eps || fabs(list[i - 1].y + 100) < eps))
|| (fabs(list[i - 1].z - (*p1).z) < eps && (fabs(list[i - 1].z - 100) < eps || fabs(list[i - 1].z + 100) < eps))) {
list[i] = *p1;
s.erase(p1);
break;
}
}
}
double s1 = 0, s2 = 0, s3 = 0;
for (int i = 0; i < n; i++) {
if (i != n - 1)
s1 += list[i].x * list[i + 1].y;
if (i != 0)
s1 -= list[i].x * list[i - 1].y;
}
s1 += list[n - 1].x * list[0].y - list[0].x * list[n - 1].y;
for (int i = 0; i < n; i++) {
if (i != n - 1)
s2 += list[i].y * list[i + 1].z;
if (i != 0)
s2 -= list[i].y * list[i - 1].z;
}
s2 += list[n - 1].y * list[0].z - list[0].y * list[n - 1].z;
for (int i = 0; i < n; i++) {
if (i != n - 1)
s3 += list[i].z * list[i + 1].x;
if (i != 0)
s3 -= list[i].z * list[i - 1].x;
}
s3 += list[n - 1].z * list[0].x - list[0].z * list[n - 1].x;
double S = sqrt(s1 * s1 + s2 * s2 + s3 * s3) / 2.0;
printf("%.2lf\n", S);
}
return 0;
}
Zhou Yi II
系列题，可以参考这里
_________________________我是被拍死的分割线_________________________
网络赛最终以刷刷ak、众大牛六题收场。bin3学长、尤波学长的表现都非常惊艳呢。rank参见下面。
看来谁都不能阻止刷刷AK的脚步了。