NotificationsYou must be signed in to change notification settings
Fork1.9k
Star9.7k

Commit50bb91b

authored

Update nearest_points.md - patch code error

1 parent4d47823 commit50bb91bCopy full SHA for 50bb91b

File tree

1 file changed

+67

-67

lines changed

src/geometry
- nearest_points.md

1 file changed

+67

-67

lines changed

`‎src/geometry/nearest_points.md‎`

Lines changed: 67 additions & 67 deletions

Original file line number	Diff line number	Diff line change
`@@ -213,85 +213,85 @@ using ll = long long;`
`213`	`213`	`using ld =longdouble;`
`214`	`214`
`215`	`215`	`structRealPoint {`
`216`		`-ld x, y;`
`217`		`-RealPoint() {}`
`218`		`-RealPoint(T x_,T y_) : x(x_), y(y_) {}`
	`216`	`+ld x, y;`
	`217`	`+RealPoint() {}`
	`218`	`+RealPoint(ld x_,ld y_) : x(x_), y(y_) {}`
`219`	`219`	`};`
`220`	`220`	`using pt = RealPoint;`
`221`	`221`
`222`	`222`	`struct CustomHash {`
`223`		`-size_t operator()(const pair<ll,ll>& p) const {`
`224`		`-static const uint64_t C = chrono::steady_clock::now().time_since_epoch().count();`
`225`		`-return C ^ ((p.first << 32) ^ p.second);`
`226`		`-}`
	`223`	`+size_t operator()(const pair<ll,ll>& p) const {`
	`224`	`+static const uint64_t C = chrono::steady_clock::now().time_since_epoch().count();`
	`225`	`+return C ^ ((p.first << 32) ^ p.second);`
	`226`	`+}`
`227`	`227`	`};`
`228`	`228`
`229`		`-ld dist(pt a,pt b) {`
`230`		`-ld dx = a.x - b.x;`
`231`		`-ld dy = a.y - b.y;`
`232`		`-return sqrt(dxdx + dydy);`
	`229`	`+ld dist(const pt& a,const pt& b) {`
	`230`	`+ld dx = a.x - b.x;`
	`231`	`+ld dy = a.y - b.y;`
	`232`	`+return sqrt(dxdx + dydy);`
`233`	`233`	`}`
`234`	`234`
`235`	`235`	`pair<pt,pt> closest_pair_of_points_rand_reals(vector<pt> P) {`
`236`	`236`	`const ld eps = 1e-9;`
`237`	`237`
`238`		`-int n = int(P.size());`
`239`		`-assert(n >= 2);`
`240`		`-unordered_map<pair<ll,ll>,vector<pt>,CustomHash> grid;`
`241`		`-grid.reserve(n);`
`242`		`-`
`243`		`-mt19937rd(chrono::system_clock::now().time_since_epoch().count());`
`244`		`-uniform_int_distribution<int>dis(0, n-1);`
`245`		`-`
`246`		`-ld d = dist(P[0], P[1]);`
`247`		`-pair<pt,pt> closest = {P[0], P[1]};`
`248`		`-`
`249`		`-auto consider_pair = [&](const pt& a, const pt& b) -> void {`
`250`		`-ld ab = dist(a, b);`
`251`		`-if (ab + eps < d) {`
`252`		`-d = ab;`
`253`		`-closest = {a, b};`
`254`		`-}`
`255`		`-};`
`256`		`-`
`257`		`-for (int i =0; i < n; ++i) {`
`258`		`-int j =dis(rd);`
`259`		`-int k =dis(rd);`
`260`		`-while (j == k)`
`261`		`- k =dis(rd);`
`262`		`-consider_pair(P[j], P[k]);`
`263`		`-}`
`264`		`-`
`265`		`-for (const pt& p : P)`
`266`		`-grid[{ll(p.x/d), ll(p.y/d)}].push_back(p);`
`267`		`-`
`268`		`-for (const auto& it : grid) { // same block`
`269`		`-int k = int(it.second.size());`
`270`		`-for (int i = 0; i < k; ++i) {`
`271`		`-for (int j = i+1; j < k; ++j)`
`272`		`-consider_pair(it.second[i], it.second[j]);`
`273`		`-}`
`274`		`-}`
	`238`	`+int n = int(P.size());`
	`239`	`+assert(n >= 2);`
	`240`	`+unordered_map<pair<ll,ll>,vector<pt>,CustomHash> grid;`
	`241`	`+grid.reserve(n);`
	`242`	`+`
	`243`	`+mt19937prng(chrono::system_clock::now().time_since_epoch().count());`
	`244`	`+uniform_int_distribution<int>uniform(0, n-1);`
	`245`	`+`
	`246`	`+ld d = dist(P[0], P[1]);`
	`247`	`+pair<pt,pt> closest = {P[0], P[1]};`
	`248`	`+`
	`249`	`+auto consider_pair = [&](const pt& a, const pt& b) -> void {`
	`250`	`+ld ab = dist(a, b);`
	`251`	`+if (ab + eps < d) {`
	`252`	`+d = ab;`
	`253`	`+closest = {a, b};`
	`254`	`+}`
	`255`	`+};`
	`256`	`+`
	`257`	`+for (int i =0; i < n; ++i) {`
	`258`	`+int j =uniform(prng);`
	`259`	`+int k =uniform(prng);`
	`260`	`+while (j == k)`
	`261`	`+ k =uniform(prng);`
	`262`	`+consider_pair(P[j], P[k]);`
	`263`	`+}`
	`264`	`+`
	`265`	`+for (const pt& p : P)`
	`266`	`+grid[{ll(p.x/d), ll(p.y/d)}].push_back(p);`
	`267`	`+`
	`268`	`+for (const auto& it : grid) { // same block`
	`269`	`+int k = int(it.second.size());`
	`270`	`+for (int i = 0; i < k; ++i) {`
	`271`	`+for (int j = i+1; j < k; ++j)`
	`272`	`+consider_pair(it.second[i], it.second[j]);`
	`273`	`+}`
	`274`	`+}`
`275`	`275`
`276`		`-for (const auto& it : grid) { // adjacent blocks`
`277`		`-auto coord = it.first;`
`278`		`-for (int dx = 0; dx <= 1; ++dx) {`
`279`		`-for (int dy = -1; dy <= 1; ++dy) {`
`280`		`-if (dx == 0 and dy == 0) continue;`
`281`		`-pair<ll,ll> neighbour = {`
`282`		`-coord.first + dx,`
`283`		`-coord.second + dy`
`284`		`-};`
`285`		`-for (const pt& p : it.second) {`
`286`		`-if (not grid.count(neighbour)) continue;`
`287`		`-for (const pt& q : grid.at(neighbour))`
`288`		`-candidate_closest(p, q);`
`289`		`-}`
`290`		`-}`
`291`		`-}`
`292`		`-}`
`293`		`-`
`294`		`-return closest;`
	`276`	`+for (const auto& it : grid) { // adjacent blocks`
	`277`	`+auto coord = it.first;`
	`278`	`+for (int dx = 0; dx <= 1; ++dx) {`
	`279`	`+for (int dy = -1; dy <= 1; ++dy) {`
	`280`	`+if (dx == 0 and dy == 0) continue;`
	`281`	`+pair<ll,ll> neighbour = {`
	`282`	`+coord.first + dx,`
	`283`	`+coord.second + dy`
	`284`	`+};`
	`285`	`+for (const pt& p : it.second) {`
	`286`	`+if (not grid.count(neighbour)) continue;`
	`287`	`+for (const pt& q : grid.at(neighbour))`
	`288`	`+consider_pair(p, q);`
	`289`	`+}`
	`290`	`+}`
	`291`	`+}`
	`292`	`+}`
	`293`	`+`
	`294`	`+return closest;`
`295`	`295`	`}`
`296`	`296`	```
`297`	`297`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Commit50bb91b

File tree

1 file changed

1 file changed

`‎src/geometry/nearest_points.md‎`

0 commit comments