thankyou

footSeq是怎么定义的

是的

因为M$的vc不支持c99标准

凸四边形构造出来四条直线，设解析式是
f_1(x,y), f_2(x,y), f_3(x,y), f_4(x,y)
将点坐标带进去，计算一下这些解析式的数值即可判断

@guest
其实无论从前边还是后边开始寻找，都是可以的
不过重要的是寻找之前把数列打乱一下，以避免在碰到有序数列的时候时间复杂度飙升的尴尬。

我觉得效率上没有什么问题了，绝对是 O(n)。

很好。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_VAL = 1024 * 4 + 1023 * 3 + 1022 * 2 + 1021;
const int UNI_16 = 0xFFFF;

struct Node {
int comb;
int cnt;
Node* next;

Node(int c, Node* n) {
comb = c;
cnt = 1;
next = n;
}
};

Node* g_value[MAX_VAL + 1];
int g_num[16];
int g_cnt8[UNI_16];

void addValue(int value, int comb);
bool card4(int set, int* num);
void clear();
void getAllCnts8();
void getAllValues4();

void addValue(int value, int comb) {
Node*& head = g_value[value];
if (head != NULL && head->comb == comb) {
head->cnt++;
}
else {
Node* node = new Node(comb, head);
head = node;
}
}

//If the cardinality of the set is 4,
//then put the 4 numbers in to array num and return true.
bool card4(int set, int* num) {
int card = 0;
int mask = 1;
for (int i = 0; i < 16; i++) {
if (mask & set) {
if (card == 4) {
card = 0;
break;
}
num[card] = g_num[i];
card++;
}
mask <<= 1;
}
return card == 4;
}

void clear() {//Free all the linked lists.
for (int i = 0; i <= MAX_VAL; i++) {
if (g_value[i] != NULL) {
Node* p = g_value[i];
while (p != NULL) {
Node* pre = p;
p = p->next;
delete pre;
}
g_value[i] = NULL;
}
}
}

void getAllCnts8() {
memset(g_cnt8, 0, sizeof(g_cnt8));
for (int val = 0; val <= MAX_VAL; val++) {
if (g_value[val] != NULL) {
for (Node* i = g_value[val]; i != NULL; i = i->next) {
for (Node* j = i->next; j != NULL; j = j->next) {
if ((i->comb & j->comb) == 0) {
g_cnt8[i->comb | j->comb] += i->cnt * j->cnt;
}
}
}
}
}
}

void getAllValues4() {
sort(g_num, g_num + 16);//Must sort, or "next_permutation()" won't work.
int num[4];
for (int comb = 0xF; comb <= 0xF000; comb++) {
if (card4(comb, num)) {
do {
int value = num[0] * 4 + num[1] * 3 + num[2] * 2 + num[3];
addValue(value, comb);
} while (next_permutation(num, num + 4));
}
}
}

bool input() {
bool hasNext = false;
cin >> g_num[0];
if (g_num[0] != 0) {
hasNext = true;
for (int i = 1; i < 16; i++) {
cin >> g_num[i];
}
}
return hasNext;
}

int solve() {
getAllValues4();
getAllCnts8();
int cnt = 0;
for (int comb8 = 0xFF; comb8 <= 0xFF00; comb8++) {
cnt += g_cnt8[comb8] * g_cnt8[comb8 ^ UNI_16];
}
return cnt / 2;
}

int main() {
memset(g_value, 0, sizeof(g_value));
int i = 1;
while (input()) {
cout << "Case " << i << ": " << solve() << endl;
clear();
i++;
}
return 0;
}

@blackball
这个地方有问题：“我分到任意一袋的概率是1/2，多的钱数为A少的钱数为a，那么我分得多交换了后手上有a/2+A/2，损失A/2-a/2，如果分得少的交换了最后得到A/2，损失是a-A/2”，交换后手上不可有a/2+A/2，若手上有A,交换后手上或者有2A，或者有A/2，不存在别的可能，引入a是无意义的。

@cepvoggg
是我自己写的；
敢问错在哪里?
我手里没有C语言编程专家这本书，你说的是不是C expert programming?

十分感谢

记录工作的点滴，继续努力！