Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- weak weak we ak we akwea weak we
- weak weak we ak weak weak we ak we
- weakweak we ak wea ak we akwe
- wea we ak we ak we akwe
- wea we ak we ak we akwe
- wea eak weak we ak we ak we
- wea wea ak we ak weak we
- we
- we ak wea ak weak we
- we ak wea weak wea eak we
- we ak we ak wea wea we we
- weak we ak we we we we
- we we ak we we we we
- we wea weak wea wea weak weak
- weak wea akw weak weak
- */
- using namespace std;
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <utility>
- #include <bitset>
- #include <set>
- #include <string>
- #include <stack>
- #include <iomanip>
- #include <map>
- #include <memory.h>
- #include <deque>
- #define pb push_back
- #define pii pair<long long,long long>
- #define F first
- #define S second
- #define LL long long
- #define mid (LB+RB)/2
- #define vvl vector <vector<LL>>
- #define vl vector <LL>
- #define mpr make_pair
- //iterators
- #define iter(x) x.begin(),x.end()
- #define aiter(a,n) a,a+n
- //loops
- #define REP(n) for (int ___=n;___--;)
- #define REP0(i,n) for (int i=0;i<n;++i)
- #define REP1(i,n) for (int i=1;i<=n;++i)
- #define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
- #define forEach(i,v) for (auto i:v)
- /*
- yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
- 8e7 so dian
- FHVirus so dian
- youou so dian
- KYW so dian
- hubert so dian
- jass so dian
- tingyu so dian
- panda so dian
- */
- //IO
- #include <iostream>
- #define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
- //testing some stuff, still under construction
- //a lot more useful while debug
- inline void print(vector <int> v){
- for (auto i:v)
- cout << i << ' ';
- cout << '\n';
- }
- inline void print(vector <int> v,char sep,char end){
- for (auto i:v)
- cout << i << sep;
- cout << end;
- }
- //constants
- const LL maxn = 200200,mod = (119 << 23) ^ 1;
- //workspace
- #include <ext/pb_ds/assoc_container.hpp>
- struct chash{
- int operator()(pii x)const {
- return (x.F * ((long long)(1e9+7)) + x.S) % mod;
- }
- };
- __gnu_pbds::gp_hash_table <pii,int,chash> ht;
- //random
- #include <random>
- inline LL dis(pii a,pii b){
- return (a.F - b.F) * (a.F - b.F) + (a.S - b.S) * (a.S - b.S);
- }
- inline pii tras(pii a,double d){
- return {a.F / d,a.S / d};
- }
- //pow
- inline long long pow_(long long n,long long k){
- long long val = 1;
- for (;k;k>>=1){
- if (k & 1)
- val = val * n % mod;
- n = n*n % mod;
- }
- return val;
- }
- pii p[maxn];
- int dx[25];
- int dy[25];
- inline void reinit(int n,double d){
- ht.clear();
- REP1(i,n){
- ht[mpr((p[i].F << 1) / d,(p[i].S << 1) / d)] = i;
- }
- }
- inline void solve(){
- int n;
- cin >> n;
- LL mnx = 0,mny = 0;
- REP1(i,n){
- cin >> p[i].F >> p[i].S;
- mnx = min(mnx,p[i].F);
- mny = min(mny,p[i].S);
- }
- REP1(i,n){
- p[i].F -= mnx;
- p[i].S -= mny;
- }
- REP1(i,n){
- swap(p[i],p[pow_(rand(),rand()) % i + 1]);
- }
- LL d = dis(p[1],p[2]);
- double srd = sqrt(d);
- REP1 (i,n){
- auto [x,y] = p[i];
- x = (x << 1) / srd;
- y = (y << 1) / srd;
- auto pd = d;
- for (int j=0;j<25;++j){
- if (ht[mpr(x + dx[j],y + dy[j])]){
- d = min(d,dis(p[i],p[ht[mpr(x + dx[j],y + dy[j])]]));
- }
- }
- if (pd > d){
- srd = sqrt(d);
- reinit (i,srd);
- }
- else
- ht[mpr(x,y)] = i;
- }
- cout << d << '\n';
- }
- int main(){
- theyRSOOOOOOOOODIAN
- srand(time(0));
- for (int i=0;i<5;++i){
- for (int j=0;j<5;++j){
- dx[i*5+j] = i - 2;
- dy[i*5+j] = j - 2;
- }
- }
- //for (int ;cin;)//use in multi-testcases and end in EOF problems
- //int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
- //cout << "Case #" << i << ": ",//use in Google, FB competitions
- solve();//always used
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement