Build a Boat

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> co;

co pts[101010];
const ld eps=1e-9;

ld getAr(co a, co b, ld x1, ld x2) {
	if (x2-x1<eps) return 0;
	ld par1=(x1-a.X)/(b.X-a.X);
	ld par2=(x2-a.X)/(b.X-a.X);
	co aa=a+par1*(b-a);
	co bb=a+par2*(b-a);
	return (bb.Y+aa.Y)*(bb.X-aa.X)/2;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ld c;
	cin>>c;
	int n;
	cin>>n;
	int leind=-1;
	ld parsa=1e7;
	for (int i=0;i<n;i++) {
		ld x,y;
		cin>>x>>y;
		if (x<parsa) {
			parsa=x;
			leind=i;
		}
		pts[i]={x,y};
	}
	pts[n]=pts[0];
	ld ar=0;
	for (int i=0;i<n;i++) {
		ar+=(pts[i].Y+pts[i+1].Y)*(pts[i].X-pts[i+1].X)/2;
	}
	ar=abs(ar);
	ld mm=floor(ar/c);
	ll m=mm;
	cout<<m<<"\n";
	int ptr1=leind;
	int ptr2=leind;
	ld acAr=0;
	ld xx=pts[leind].X;
	cout<<setprecision(15);
	for (ll i=1;i<m;i++) {
		while (acAr<(i*ar)/m) {
			while (ptr1>0 && pts[ptr1-1].X-xx<eps) ptr1--;
			if (ptr1==0) ptr1=n;
			while (ptr1>0 && pts[ptr1-1].X-xx<eps) ptr1--;
			while (ptr2<n && pts[ptr2+1].X-xx<eps) ptr2++;
			if (ptr2==n) ptr2=0;
			while (ptr2<n && pts[ptr2+1].X-xx<eps) ptr2++;
			ld x2=min(pts[ptr1-1].X,pts[ptr2+1].X);
//			cerr<<x2<<endl;
			if (acAr+getAr(pts[ptr1-1],pts[ptr1],xx,x2)-getAr(pts[ptr2+1],pts[ptr2],xx,x2)<(i*ar)/m) {
				acAr+=getAr(pts[ptr1-1],pts[ptr1],xx,x2)-getAr(pts[ptr2+1],pts[ptr2],xx,x2);
				xx=x2;
			} else {
//				cerr<<"taa"<<endl;
				ld lo=xx;
				ld hi=x2;
				for (int ii=0;ii<100;ii++) {
					ld mid=(lo+hi)/2;
					if (acAr+getAr(pts[ptr1-1],pts[ptr1],xx,mid)-getAr(pts[ptr2+1],pts[ptr2],xx,mid)<(i*ar)/m) {
						lo=mid;
					} else hi=mid;
				}
				acAr=(i*ar)/m;
				xx=lo;
			}
		}
		cout<<xx<<"\n";
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED