#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <cassert>
#include <tuple>
struct Vector3
{
float x, y, z;
Vector3() {}
Vector3(float xx, float yy, float zz)
{
x = xx, y = yy, z = zz;
}
inline bool operator==(const Vector3& other) const
{
return x == other.x && y == other.y && z == other.z;
}
inline bool operator<(const Vector3& other) const
{
return std::tie(x, y, z) < std::tie(other.x, other.y, other.z);
}
friend std::ostream& operator<<(std::ostream& stream, const Vector3& vector);
};
std::ostream& operator<<(std::ostream& stream, const Vector3& vector)
{
return stream
<< "("
<< std::setw(2) << std::setfill(' ') << vector.x << ", "
<< std::setw(2) << std::setfill(' ') << vector.y << ", "
<< std::setw(2) << std::setfill(' ') << vector.z
<< ")";
}
struct Edge
{
Vector3 EndPoints[2];
Edge() {}
Edge(Vector3 p, Vector3 q)
{
// swap order
if (q < p) { using std::swap; swap(p, q); } // the invariant
EndPoints[0] = p;
EndPoints[1] = q;
}
inline bool operator==(const Edge& other) const {
return std::tie(EndPoints[0], EndPoints[1]) == std::tie(other.EndPoints[0], other.EndPoints[1]);
}
friend std::ostream& operator<<(std::ostream& stream, const Edge& vector);
friend std::ostream& operator<<(std::ostream& stream, const Edge* vector);
};
struct EdgePtrEqual {
bool operator()(Edge const* a, Edge const* b) const {
return *a == *b;
}
};
std::ostream& operator<<(std::ostream& stream, const Edge& edge)
{
return stream << edge.EndPoints[0] << " -- " << edge.EndPoints[1];
}
std::ostream& operator<<(std::ostream& stream, const Edge* edge)
{
return stream << edge->EndPoints[0] << " -- " << edge->EndPoints[1];
}
namespace std
{
template <> struct hash<Edge>
{
std::size_t operator()(const Edge& edge) const {
Vector3 p0 = edge.EndPoints[0];
Vector3 p1 = edge.EndPoints[1];
assert(p0 < p1); // the invariant
auto hash_p = [](Vector3 const& p) { return (unsigned(p.x*73856093u) ^ unsigned(p.y*19349663u) ^ unsigned(p.z*83492791u)) % 1024u; };
return hash_p(p0) ^ (hash_p(p1) << 3);
}
};
template <> struct hash<Edge*> {
std::size_t operator()(const Edge* edge) const {
return hash<Edge>()(*edge);
}
};
}
using EdgeSet = std::unordered_set<Edge, std::hash<Edge>>;
using EdgePtrSet = std::unordered_set<Edge*, std::hash<Edge*>, EdgePtrEqual>;
void add_edge(EdgeSet& table, Edge edge)
{
EdgeSet::const_iterator it = table.find(edge);
if (it == table.end()) table.insert(edge);
else std::cout << "Table already contains edge " << edge << std::endl;
}
void add_edge(EdgePtrSet& table, Edge* edge)
{
EdgePtrSet::const_iterator it = table.find(edge);
if (it == table.end()) table.insert(edge);
else std::cout << "Table already contains edge " << edge << std::endl;
}
void print_table(EdgeSet& table)
{
std::cout << std::endl;
std::cout << "Table has " << table.size() << " elements:" << std::endl;
for (auto it = table.begin(); it != table.end(); ++it)
std::cout << *it << std::endl;
std::cout << std::endl;
}
void print_table(EdgePtrSet& table)
{
std::cout << std::endl;
std::cout << "Table has " << table.size() << " elements:" << std::endl;
for (auto it = table.begin(); it != table.end(); ++it)
std::cout << *(*it) << std::endl;
std::cout << std::endl;
}
int main()
{
EdgeSet table;
EdgePtrSet ptable;
Edge e0(Vector3( 1.f, 0.f, 0.f), Vector3(-1.f, 0.f, 0.f));
Edge e1(Vector3(-1.f, 0.f, 0.f), Vector3( 1.f, 0.f, 0.f));
add_edge(table, e0);
add_edge(table, e1);
print_table(table);
add_edge(ptable, &e0);
add_edge(ptable, &e1);
print_table(ptable);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPHVub3JkZXJlZF9zZXQ+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8dHVwbGU+CgpzdHJ1Y3QgVmVjdG9yMwp7CiAgICBmbG9hdCB4LCB5LCB6OwoKICAgIFZlY3RvcjMoKSB7fQoKICAgIFZlY3RvcjMoZmxvYXQgeHgsIGZsb2F0IHl5LCBmbG9hdCB6eikKICAgIHsKICAgICAgICB4ID0geHgsIHkgPSB5eSwgeiA9IHp6OwogICAgfQoKICAgIGlubGluZSBib29sIG9wZXJhdG9yPT0oY29uc3QgVmVjdG9yMyYgb3RoZXIpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuIHggPT0gb3RoZXIueCAmJiB5ID09IG90aGVyLnkgJiYgeiA9PSBvdGhlci56OwogICAgfQoKICAgIGlubGluZSBib29sIG9wZXJhdG9yPChjb25zdCBWZWN0b3IzJiBvdGhlcikgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gc3RkOjp0aWUoeCwgeSwgeikgPCBzdGQ6OnRpZShvdGhlci54LCBvdGhlci55LCBvdGhlci56KTsKICAgIH0KCiAgICBmcmllbmQgc3RkOjpvc3RyZWFtJiBvcGVyYXRvcjw8KHN0ZDo6b3N0cmVhbSYgc3RyZWFtLCBjb25zdCBWZWN0b3IzJiB2ZWN0b3IpOwp9OwoKc3RkOjpvc3RyZWFtJiBvcGVyYXRvcjw8KHN0ZDo6b3N0cmVhbSYgc3RyZWFtLCBjb25zdCBWZWN0b3IzJiB2ZWN0b3IpCnsKICAgIHJldHVybiBzdHJlYW0gCiAgICAgICAgPDwgIigiIAogICAgICAgIDw8IHN0ZDo6c2V0dygyKSA8PCBzdGQ6OnNldGZpbGwoJyAnKSA8PCB2ZWN0b3IueCA8PCAiLCAiIAogICAgICAgIDw8IHN0ZDo6c2V0dygyKSA8PCBzdGQ6OnNldGZpbGwoJyAnKSA8PCB2ZWN0b3IueSA8PCAiLCAiIAogICAgICAgIDw8IHN0ZDo6c2V0dygyKSA8PCBzdGQ6OnNldGZpbGwoJyAnKSA8PCB2ZWN0b3IueiAKICAgICAgICA8PCAiKSI7Cn0KCnN0cnVjdCBFZGdlCnsKICAgIFZlY3RvcjMgRW5kUG9pbnRzWzJdOwoKICAgIEVkZ2UoKSB7fQoKICAgIEVkZ2UoVmVjdG9yMyBwLCBWZWN0b3IzIHEpCiAgICB7CiAgICAgICAgLy8gc3dhcCBvcmRlcgogICAgICAgIGlmIChxIDwgcCkgeyB1c2luZyBzdGQ6OnN3YXA7IHN3YXAocCwgcSk7IH0gLy8gdGhlIGludmFyaWFudAogICAgICAgIEVuZFBvaW50c1swXSA9IHA7CiAgICAgICAgRW5kUG9pbnRzWzFdID0gcTsKICAgIH0KCiAgICBpbmxpbmUgYm9vbCBvcGVyYXRvcj09KGNvbnN0IEVkZ2UmIG90aGVyKSBjb25zdCB7CiAgICAgICAgcmV0dXJuIHN0ZDo6dGllKEVuZFBvaW50c1swXSwgRW5kUG9pbnRzWzFdKSA9PSBzdGQ6OnRpZShvdGhlci5FbmRQb2ludHNbMF0sIG90aGVyLkVuZFBvaW50c1sxXSk7CiAgICB9CgogICAgZnJpZW5kIHN0ZDo6b3N0cmVhbSYgb3BlcmF0b3I8PChzdGQ6Om9zdHJlYW0mIHN0cmVhbSwgY29uc3QgRWRnZSYgdmVjdG9yKTsKICAgIGZyaWVuZCBzdGQ6Om9zdHJlYW0mIG9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtJiBzdHJlYW0sIGNvbnN0IEVkZ2UqIHZlY3Rvcik7Cn07CgpzdHJ1Y3QgRWRnZVB0ckVxdWFsIHsKICAgIGJvb2wgb3BlcmF0b3IoKShFZGdlIGNvbnN0KiBhLCBFZGdlIGNvbnN0KiBiKSBjb25zdCB7CiAgICAgICAgcmV0dXJuICphID09ICpiOwogICAgfQp9OwoKc3RkOjpvc3RyZWFtJiBvcGVyYXRvcjw8KHN0ZDo6b3N0cmVhbSYgc3RyZWFtLCBjb25zdCBFZGdlJiBlZGdlKQp7CiAgICByZXR1cm4gc3RyZWFtIDw8IGVkZ2UuRW5kUG9pbnRzWzBdIDw8ICIgLS0gIiA8PCBlZGdlLkVuZFBvaW50c1sxXTsKfQoKc3RkOjpvc3RyZWFtJiBvcGVyYXRvcjw8KHN0ZDo6b3N0cmVhbSYgc3RyZWFtLCBjb25zdCBFZGdlKiBlZGdlKQp7CiAgICByZXR1cm4gc3RyZWFtIDw8IGVkZ2UtPkVuZFBvaW50c1swXSA8PCAiIC0tICIgPDwgZWRnZS0+RW5kUG9pbnRzWzFdOwp9CgoKbmFtZXNwYWNlIHN0ZAp7CiAgICB0ZW1wbGF0ZSA8PiBzdHJ1Y3QgaGFzaDxFZGdlPgogICAgewogICAgICAgIHN0ZDo6c2l6ZV90IG9wZXJhdG9yKCkoY29uc3QgRWRnZSYgZWRnZSkgY29uc3QgewogICAgICAgICAgICBWZWN0b3IzIHAwID0gZWRnZS5FbmRQb2ludHNbMF07CiAgICAgICAgICAgIFZlY3RvcjMgcDEgPSBlZGdlLkVuZFBvaW50c1sxXTsKCiAgICAgICAgICAgIGFzc2VydChwMCA8IHAxKTsgLy8gdGhlIGludmFyaWFudAoKICAgICAgICAgICAgYXV0byBoYXNoX3AgPSBbXShWZWN0b3IzIGNvbnN0JiBwKSB7IHJldHVybiAodW5zaWduZWQocC54KjczODU2MDkzdSkgXiB1bnNpZ25lZChwLnkqMTkzNDk2NjN1KSBeIHVuc2lnbmVkKHAueio4MzQ5Mjc5MXUpKSAlIDEwMjR1OyB9OwoKICAgICAgICAgICAgcmV0dXJuIGhhc2hfcChwMCkgXiAoaGFzaF9wKHAxKSA8PCAzKTsKICAgICAgICB9CiAgICB9OwoKICAgIHRlbXBsYXRlIDw+IHN0cnVjdCBoYXNoPEVkZ2UqPiB7CiAgICAgICAgc3RkOjpzaXplX3Qgb3BlcmF0b3IoKShjb25zdCBFZGdlKiBlZGdlKSBjb25zdCB7IAogICAgICAgICAgICByZXR1cm4gaGFzaDxFZGdlPigpKCplZGdlKTsgCiAgICAgICAgfQogICAgfTsKfQoKdXNpbmcgRWRnZVNldCAgICA9IHN0ZDo6dW5vcmRlcmVkX3NldDxFZGdlLCAgc3RkOjpoYXNoPEVkZ2U+PjsKdXNpbmcgRWRnZVB0clNldCA9IHN0ZDo6dW5vcmRlcmVkX3NldDxFZGdlKiwgc3RkOjpoYXNoPEVkZ2UqPiwgRWRnZVB0ckVxdWFsPjsKCnZvaWQgYWRkX2VkZ2UoRWRnZVNldCYgdGFibGUsIEVkZ2UgZWRnZSkKewogICAgRWRnZVNldDo6Y29uc3RfaXRlcmF0b3IgaXQgPSB0YWJsZS5maW5kKGVkZ2UpOwogICAgaWYgKGl0ID09IHRhYmxlLmVuZCgpKSB0YWJsZS5pbnNlcnQoZWRnZSk7CiAgICBlbHNlIHN0ZDo6Y291dCA8PCAiVGFibGUgYWxyZWFkeSBjb250YWlucyBlZGdlICIgPDwgZWRnZSA8PCBzdGQ6OmVuZGw7Cn0KCnZvaWQgYWRkX2VkZ2UoRWRnZVB0clNldCYgdGFibGUsIEVkZ2UqIGVkZ2UpCnsKICAgIEVkZ2VQdHJTZXQ6OmNvbnN0X2l0ZXJhdG9yIGl0ID0gdGFibGUuZmluZChlZGdlKTsKICAgIGlmIChpdCA9PSB0YWJsZS5lbmQoKSkgdGFibGUuaW5zZXJ0KGVkZ2UpOwogICAgZWxzZSBzdGQ6OmNvdXQgPDwgIlRhYmxlIGFscmVhZHkgY29udGFpbnMgZWRnZSAiIDw8IGVkZ2UgPDwgc3RkOjplbmRsOwp9CgoKdm9pZCBwcmludF90YWJsZShFZGdlU2V0JiB0YWJsZSkKewogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCAiVGFibGUgaGFzICIgPDwgdGFibGUuc2l6ZSgpIDw8ICIgZWxlbWVudHM6IiA8PCBzdGQ6OmVuZGw7CgogICAgZm9yIChhdXRvIGl0ID0gdGFibGUuYmVnaW4oKTsgaXQgIT0gdGFibGUuZW5kKCk7ICsraXQpCiAgICAgICAgc3RkOjpjb3V0IDw8ICppdCA8PCBzdGQ6OmVuZGw7CgogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKfQoKdm9pZCBwcmludF90YWJsZShFZGdlUHRyU2V0JiB0YWJsZSkKewogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIHN0ZDo6Y291dCA8PCAiVGFibGUgaGFzICIgPDwgdGFibGUuc2l6ZSgpIDw8ICIgZWxlbWVudHM6IiA8PCBzdGQ6OmVuZGw7CgogICAgZm9yIChhdXRvIGl0ID0gdGFibGUuYmVnaW4oKTsgaXQgIT0gdGFibGUuZW5kKCk7ICsraXQpCiAgICAgICAgc3RkOjpjb3V0IDw8ICooKml0KSA8PCBzdGQ6OmVuZGw7CgogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKfQoKCmludCBtYWluKCkKewogICAgRWRnZVNldCB0YWJsZTsKICAgIEVkZ2VQdHJTZXQgcHRhYmxlOwoKICAgIEVkZ2UgZTAoVmVjdG9yMyggMS5mLCAgMC5mLCAgMC5mKSwgVmVjdG9yMygtMS5mLCAgMC5mLCAgMC5mKSk7CiAgICBFZGdlIGUxKFZlY3RvcjMoLTEuZiwgIDAuZiwgIDAuZiksIFZlY3RvcjMoIDEuZiwgIDAuZiwgIDAuZikpOwoKICAgIGFkZF9lZGdlKHRhYmxlLCBlMCk7CiAgICBhZGRfZWRnZSh0YWJsZSwgZTEpOwoKICAgIHByaW50X3RhYmxlKHRhYmxlKTsKCiAgICBhZGRfZWRnZShwdGFibGUsICZlMCk7CiAgICBhZGRfZWRnZShwdGFibGUsICZlMSk7CgogICAgcHJpbnRfdGFibGUocHRhYmxlKTsKCiAgICByZXR1cm4gMDsKfQo=