結果
問題 | No.168 ものさし |
ユーザー |
![]() |
提出日時 | 2015-03-19 23:52:37 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 2,052 bytes |
コンパイル時間 | 1,132 ms |
コンパイル使用メモリ | 97,732 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 06:55:50 |
合計ジャッジ時間 | 2,186 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
#include <string> #include <vector> #include<iostream> #include<cstdio> #include<cstdlib> #include<stack> #include<queue> #include<cmath> #include<algorithm> #include<functional> #include<list> #include<deque> #include<bitset> #include<set> #include<map> #include<unordered_map> #include<cstring> #include<sstream> #include<complex> #include<iomanip> #include<numeric> #define X first #define Y second #define pb push_back #define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X)) #define rrep(X,Y) for (int (X) = (Y-1);(X) >=0;--(X)) #define repe(X,Y) for ((X) = 0;(X) < (Y);++(X)) #define peat(X,Y) for (;(X) < (Y);++(X)) #define all(X) (X).begin(),(X).end() #define rall(X) (X).rbegin(),(X).rend() using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<class T> using vv=vector<vector<T>>; template<class T> ostream& operator<<(ostream &os, const vector<T> &t) { os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;} template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";} struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; int main(){ ios_base::sync_with_stdio(false); cout<<fixed<<setprecision(0); int i,j,k; ll n; cin>>n; vector<ll> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; ll l=-1,r=2e8,m,m2,dx,dy; while(r-l>1){ m=(r+l)/2; m2=m*m*100; UnionFind uf(n); rep(i,n)for(j=i+1;j<n;++j){ dx=x[i]-x[j]; dy=y[i]-y[j]; if(dx*dx+dy*dy<=m2) uf.unionSet(i,j); } if(uf.findSet(0,n-1)) r=m; else l=m; } cout<<r*10<<endl; return 0; }