| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 688439 |
2023-01-27T12:59:32 Z |
browntoad |
Plot (POI11_wyk) |
C++14 |
|
29440 ms |
24872 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=1e5+5;
const double PI=acos(-1);
ll pw(ll x, ll p, ll m=mod){
ll ret=1;
while (p>0){
if (p&1){
ret*=x;
ret%=m;
}
x*=x;
x%=m;
p>>=1;
}
return ret;
}
ll inv(ll a, ll m=mod){
return pw(a,m-2);
}
//=======================================================================================
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxpw = 18;
int n, m;
const double eps = 0;
struct Point{
double x, y;
void operator =(Point b){
x=b.x;
y=b.y;
}
bool operator <(Point b){
if (x==b.x) return y<b.y;
return x<b.x;
}
Point operator +(Point b){
return {x+b.x, y+b.y};
}
Point operator -(Point b){
return {x-b.x, y-b.y};
}
Point operator *(double k){
return {x*k, y*k};
}
double dot(Point a, Point b){
return a.x*b.x+a.y*b.y;
}
double cross(Point a, Point b){
return a.x*b.y-a.y*b.x;
}
double dis2(Point a, Point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
Point midpoint(Point a, Point b){
return (a+b)*0.5;
}
pair<Point, Point> perpbisector(pair<Point, Point> a){
Point temp = a.s-a.f;
temp = {temp.y, -temp.x};
return {midpoint(a.f, a.s), midpoint(a.f, a.s)+temp};
}
Point intersect(pair<Point, Point> a, pair<Point, Point> b){
double temp = cross(b.f-a.f, a.s-a.f);
temp = temp / (temp + cross(a.s-a.f, b.s-a.f));
return b.f+((b.s-b.f)*temp);
}
pair<Point, double> circum(Point a, Point b, Point c){
// if a, b, c are collinear
if (b<a) swap(a, b);
if (c<a) swap(a, c);
if (c<b) swap(b, c);
Point ret;
if (abs(cross(b-a, c-a)) < eps){
ret=midpoint(a, c);
}
else {
ret=intersect(perpbisector({a, b}), perpbisector({a, c}));
}
return {ret, dis2(ret, a)};
}
}point;
vector<Point> vc;
vector<Point> tmpvc;
pair<Point, double> triv(vector<Point> &t){
if (SZ(t)==0){
return {{5, 5}, 0};
}
if (SZ(t)==1){
return {t[0], 0};
}
if (SZ(t)==2){
Point tv;
tv=point.midpoint(t[0], t[1]);
return {tv, point.dis2(tv, t[0])};
}
if (SZ(t)==3){
return point.circum(t[0], t[1], t[2]);
}
assert(0);
}
pair<Point, double> welzl(vector<Point> &t, int id){
if (id==-1 || SZ(t)==3){
return triv(t);
}
pair<Point, double> temp = welzl(t, id-1);
if (point.dis2(temp.f, tmpvc[id]) > temp.s + eps){
vector<Point> t2;
REP(i, SZ(t)) t2.pb(t[i]);
t2.pb(tmpvc[id]);
temp = welzl(t2, id-1);
return temp;
}
else return temp;
}
pair<Point, double> minenclosingcircle(int l, int r){
tmpvc.clear();
FOR(i, l, r+1) tmpvc.pb(vc[i]);
shuffle(ALL(tmpvc), rng);
vector<Point> tmp;
pair<Point, double> cur = welzl(tmp, SZ(tmpvc)-1);
return cur;
}
vector<Point> res;
bool check(double g){
res.clear();
int cur = 0, cnt = 1;
pair<Point, double> tmp;
int bsl=0, bsr=0, bsmid;
while(cnt<=m){
REP(j, mxpw){
if ((1<<j)+cur-1>=n-1){
tmp = minenclosingcircle(cur, n-1);
if (tmp.s<=g+eps){
res.pb(tmp.f);
return 1;
}
else {
bsl=(1<<(j-1))-1+cur;
bsr=n-1;
break;
}
}
else{
tmp = minenclosingcircle(cur, cur+(1<<j)-1);
if (tmp.s>g+eps){
bsl=(1<<(j-1))-1+cur;
bsr=(1<<j)-1+cur;
break;
}
}
}
while(bsl<bsr){
bsmid = (bsl+bsr+1)/2;
tmp = minenclosingcircle(cur, bsmid);
if (tmp.s>g+eps){
bsr=bsmid-1;
}
else bsl=bsmid;
}
tmp = minenclosingcircle(cur, bsl);
res.pb(tmp.f);
cur=bsl+1;
assert(cur<n);
cnt++;
}
return 0;
}
signed main (){
IOS();
cin>>n>>m;
cout<<fixed<<setprecision(10);
vc.resize(n);
REP(i, n){
cin>>vc[i].x>>vc[i].y;
}
double l=0.0, r=3e12;
double mid;
double p=-1;
REP(k, 90){
mid = (l+r)/2;
if (check(mid)){
p=mid;
r=mid;
}
else {
l=mid;
}
}
check(p);
cout<<sqrt(p)<<endl;
cout<<SZ(res)<<endl;
REP(i, SZ(res)){
cout<<res[i].x<<' '<<res[i].y<<endl;
}
}
/*
2:53
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
340 KB |
Output is correct |
| 2 |
Correct |
6 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
528 KB |
Output is correct |
| 2 |
Correct |
6 ms |
540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
340 KB |
Output is correct |
| 2 |
Correct |
99 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
520 KB |
Output is correct |
| 2 |
Correct |
142 ms |
520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
506 ms |
1452 KB |
Output is correct |
| 2 |
Correct |
619 ms |
1460 KB |
Output is correct |
| 3 |
Correct |
520 ms |
1456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6605 ms |
10564 KB |
Output is correct |
| 2 |
Correct |
5748 ms |
10568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12583 ms |
20696 KB |
Output is correct |
| 2 |
Correct |
24084 ms |
21344 KB |
Output is correct |
| 3 |
Correct |
5430 ms |
7300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28892 ms |
20804 KB |
Output is correct |
| 2 |
Correct |
29440 ms |
20808 KB |
Output is correct |
| 3 |
Correct |
13942 ms |
8676 KB |
Output is correct |
| 4 |
Correct |
6731 ms |
20708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1133 ms |
20800 KB |
Output is correct |
| 2 |
Correct |
5861 ms |
24872 KB |
Output is correct |
| 3 |
Correct |
14258 ms |
20696 KB |
Output is correct |
