oj.uz

Submission #199930

# Submission time Handle Problem Language Result Execution time Memory
199930 2020-02-04T06:49:20 Z gs14004 Plot (POI11_wyk) C++17
100 / 100
 7994 ms 9700 KB 
#include<bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 100005;
const int mod = 1e9 + 7;
const double eps = 1e-1;

using Point = complex<double>;
struct Circle{ Point p; double r; };
double dot(Point p, Point q){ return p.real() * p.real() + p.imag() * p.imag(); }
double dist(Point p, Point q){ return dot(q - p, q - p); }
double area2(Point p, Point q){ return p.real() * q.imag() - q.real() * p.imag(); }
bool in(const Circle& c, Point p){ return dist(c.p, p) < c.r + eps; }
Circle INVAL = Circle{Point(0, 0), -1};
Circle mCC(Point a, Point b, Point c){
	b -= a; c -= a;
	double d = 2*area2(b, c); if(abs(d) < eps) return INVAL;
	Point ans = (c*dot(b, b) - b*dot(c, c)) * Point(0, -1) / d;
	return Circle{a + ans, dist(Point(0, 0), ans)};
}

mt19937 gen(0x94949); 

Circle solve(vector<Point> p){
	if(sz(p) == 1){
		return Circle{p[0], 0};
	}
	if(sz(p) == 2){
		return Circle{(p[0] + p[1]) / 2.0, dist(p[0], p[1]) / 4.0};
	}

	shuffle(p.begin(), p.end(), gen);
	Circle c = INVAL;
	for(int i=0; i<p.size(); ++i) if(c.r<0 ||!in(c, p[i])){
		c = Circle{p[i], 0};
		for(int j=0; j<=i; ++j) if(!in(c, p[j])){
			Circle ans{(p[i]+p[j])*0.5, dist(p[i], p[j])*0.25};
			if(c.r == 0) { c = ans; continue; }
			Circle l, r; l = r = INVAL;
			Point pq = p[j]-p[i];
			for(int k=0; k<=j; ++k) if(!in(ans, p[k])) {
				double a2 = area2(pq, p[k]-p[i]);
				Circle c = mCC(p[i], p[j], p[k]);
				if(c.r<0) continue;
                double b2 = area2(pq, c.p-p[i]) ;
				if(a2 > 0 && (l.r<0||b2 > area2(pq, l.p-p[i]))) l = c;
				else if(a2 < 0 && (r.r<0||b2 < area2(pq, r.p-p[i]))) r = c;
			}
			if(l.r<0&&r.r<0) c = ans;
			else if(l.r<0) c = r;
			else if(r.r<0) c = l;
			else c = l.r<=r.r?l:r;
		}
	}
	return c;
}

int n, m;
Point a[MAXN];

Circle cost(int l, int r){
	return solve(vector<Point>(a + l, a + r + 1));
}

vector<Circle> trace;

bool trial(double x){
	trace.clear();
	int cur = 0;
	for(int i=0; i<m; i++){
		int st = cur, ed = n - m + i;
		int p = 1;
		while(cur + p - 1 <= ed && cost(cur, cur + p - 1).r <= x) p <<= 1;
		ed = min(ed, cur + p - 1);
		st = cur + (p / 2) - 1;
		while(st != ed){
			int mid = (st + ed + 1) / 2;
			if(cost(cur, mid).r > x) ed = mid - 1;
			else st = mid;
		}
		trace.push_back(cost(cur, st));
		cur = st + 1;
	}
	return cur == n;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		int x = rand() % 2000001 - 1000000;
		int y = rand() % 2000001 - 1000000;
		scanf("%d %d",&x,&y);
		a[i] = Point(x, y);
	}
	double s = 0, e = 2e12;
	while(sqrt(e) - sqrt(s) > 5e-7){
		double mid = (s+e)/2;
		if(trial(mid)) e = mid;
		else s = mid;
	}
	trial(e);
	printf("%.10f\n", sqrt(e));
	printf("%d\n", sz(trace));
	for(auto &i : trace) printf("%.10f %.10f\n", i.p.real(), i.p.imag());
}

Compilation message

wyk.cpp: In function 'Circle solve(std::vector<std::complex<double> >)':
wyk.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<p.size(); ++i) if(c.r<0 ||!in(c, p[i])){
               ~^~~~~~~~~
wyk.cpp: In function 'int main()':
wyk.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
wyk.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 248 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 376 KB Output is correct
2 Correct 23 ms 376 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 376 KB Output is correct
2 Correct 20 ms 504 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 376 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 376 KB Output is correct
2 Correct 43 ms 376 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 716 KB Output is correct
2 Correct 200 ms 504 KB Output is correct
3 Correct 131 ms 632 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2834 ms 2852 KB Output is correct
2 Correct 1990 ms 2296 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3960 ms 3884 KB Output is correct
2 Correct 6240 ms 5848 KB Output is correct
3 Correct 766 ms 9700 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7519 ms 5252 KB Output is correct
2 Correct 7445 ms 5024 KB Output is correct
3 Correct 5076 ms 3704 KB Output is correct
4 Correct 7994 ms 5104 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4564 ms 4984 KB Output is correct
2 Correct 884 ms 8292 KB Output is correct
3 Correct 4691 ms 5024 KB Output is correct