Editorial for Đường phố mùa lễ hội
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <utility> using namespace std; int clockwise(int x, int y, int xx, int yy, int xxx, int yyy) { return 1LL * (x - xx) * (y + yy) + 1LL * (xx - xxx) * (yy + yyy) + 1LL * (xxx - x) * (yyy + y) < 0; } int main() { int n, hullX[100100], hullY[100100], yIntercept[100100], H = 0, y; cin >> n; for (int x = 1; x <= n; x++) { scanf("%d", &y); while (H > 1 && clockwise(x, y, hullX[H - 1], hullY[H - 1], hullX[H - 2], hullY[H - 2])) H--; hullX[H] = x; hullY[H++] = y; } for (int i = 0; i + 1 < H; i++) { double slope = 1.0 * (hullY[i] - hullY[i + 1]) / (hullX[i] - hullX[i + 1]); yIntercept[i] = int(hullY[i] - slope * hullX[i] + 1e-8); } yIntercept[H - 1] = 1000111222; cin >> n; while (n--) { scanf("%d", &y); int i = lower_bound(yIntercept, yIntercept + H, y) - yIntercept; double slope = 1.0 * (hullY[i] - y) / hullX[i]; printf("%.6lf\n", 1 / slope); } }
Code mẫu của happyboy99x
#include<cstdio> #define long long long struct Line { long a, b, lim; Line(long a = 0, long b = 0, long lim = 0): a (a), b (b), lim (lim) {} double val(long x) const { return 1. * (a - x) / b; } long xCut(const Line &x) const { return (a * x.b - b * x.a) / (x.b - b); } bool bad(const Line &x, const Line &y) const { return (a*x.b - b*x.a) * (y.b-b) >= (a*y.b - b*y.a) * (x.b-b); } }; const int N = 1e5, INF = 2e9; Line l[N]; int nLine; void addLine(const Line &a) { while(nLine > 1 && l[nLine-2].bad(l[nLine-1], a)) --nLine; if(nLine > 0) l[nLine-1].lim = l[nLine-1].xCut(a); l[nLine++] = a; } void enter() { int n; scanf("%d", &n); for(int i = 0; i < n; ++i) { int a; scanf("%d", &a); addLine(Line(a, i + 1, INF)); } } void solve() { int m; scanf("%d", &m); for(int i = 0; i < m; ++i) { int s; scanf("%d", &s); int low = 0, high = nLine - 1; while(low < high) { int mid = (low + high) >> 1; if(l[mid].lim < s) low = mid + 1; else high = mid; } printf("%.6lf\n", 1 / l[low].val(s)); } } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<LL, LL> #define X first #define Y second #define VI vector<int> const int N = 100005; using namespace std; void operator -= (II &a, II b) {a.X -= b.X; a.Y -= b.Y;} bool ccw(II a, II b, II c) {c -= b; b -= a; return b.X * c.Y >= b.Y * c.X;} vector<II> hull; II a[N], s[N]; double ans[N]; int n, m; int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> m; FOR(i, 0, m) { cin >> a[i].Y; a[i].X = i + 1; } sort(a, a + m); #define nn (int(hull.size())) FOR(i, 0, m) { while (nn > 1 && ccw(hull[nn - 2], hull[nn - 1], a[i])) hull.pop_back(); hull.PB(a[i]); } cin >> n; FOR(i, 0, n) { cin >> s[i].X; s[i].Y = i; } sort(s, s + n); int j = 0; FOR(i, 0, n) { while (j + 1 < nn && ccw(MP(0, s[i].X), hull[j], hull[j + 1])) j++; ans[s[i].Y] = (double)hull[j].X / (hull[j].Y - s[i].X); } FOR(i, 0, n) cout << setprecision(6) << fixed << ans[i] << '\n'; return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> using namespace std; typedef long long ll; typedef double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) //#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) //#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = {0, +1, 0, -1}; const int dc[] = {+1, 0, -1, 0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const ll mod = (ll)1e9 + 7; #define maxn 100005 int cmp(ll x, ll y){ if(x == y) return 0; return x < y ? -1 : 1; } struct Point { ll x, y; Point(){}; Point(ll _x, ll _y){ x = _x; y = _y; } bool operator ==(const Point& that) const { return (cmp(x, that.x) == 0 && cmp(y, that.y) == 0); } bool operator <(const Point& that) const { if (cmp(x, that.x) != 0) return cmp(x, that.x) < 0; return cmp(y, that.y) < 0; } }; ll sqrdist(Point P0, Point P1){ return sqr(P0.x - P1.x) + sqr(P0.y - P1.y); } int ccw(Point p0, Point p1, Point p2) { ll dx1 = p1.x - p0.x, dy1 = p1.y - p0.y; ll dx2 = p2.x - p0.x, dy2 = p2.y - p0.y; return cmp(dx1 * dy2 - dx2 * dy1, 0); } Point O; bool cmp_angle(Point P1, Point P2) { int ret = ccw(O, P1, P2); if (ret != 0) return ret > 0; return sqrdist(O, P1) < sqrdist(O, P2); } int convex_hull(Point a[], int n) { if (n <= 3) return n; int imin = 0; Rep(i, n) if (a[i].y < a[imin].y || (a[i].y == a[imin].y && a[i].x < a[imin].x)) imin = i; swap(a[imin], a[0]); O = a[0]; sort(a + 1, a + n, cmp_angle); int m = 2; For(i, 2, n - 1) { while (m > 1 && ccw(a[i], a[m - 1], a[m - 2]) >= 0) --m; swap(a[m], a[i]); ++m; } return m; } int n, m, x; II S[maxn]; ld res[maxn]; Point P[maxn * 2]; ld cal(ll h, int id){ ld res = P[id].x * (ld)(1.0) / (P[id].y - h); if(h >= P[id].y) res = linf - P[id].y; return res; } int main() { // freopen("in.txt", "r", stdin); cin >> n; Rep(i, n){ scanf("%d", &x); P[i] = Point(i + 1, x); } n = convex_hull(P, n); For(i, n, n + n) P[i] = P[i - n]; cin >> m; S[0] = mp(0, 0); For(i, 1, m){ scanf("%d", &S[i].fi); S[i].se = i; } sort(S + 1, S + m + 1); Rep(i, n / 2) swap(P[i], P[n - 1 - i]); ll MIN = linf; int run = -1; Rep(i, n) if(cal(0, i) < MIN){ MIN = cal(0, i); run = i; } For(i, 1, m){ while(cal(S[i].fi, run) > cal(S[i].fi, run + 1)) run++; res[S[i].se] = cal(S[i].fi, run); } For(i, 1, m){ printf("%.6lf\n", res[i]); } // getch(); }
Code mẫu của skyvn97
#include<bits/stdc++.h> #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) #define fi first #define se second using namespace std; const double INF=1e9+7; const double eps=1e-7; typedef pair<double,double> dd; bool cmp(const dd &a,const dd &b) { return (a.fi<b.fi); } class ConvexHull { private: vector<dd> v; double L,R; int sz; bool empty; public: ConvexHull() { L=0.0;R=0.0;sz=0;empty=true; } ConvexHull(double l,double r,int n) { L=l;R=r; empty=true; v=vector<dd>(2*n+7); sz=2; v[0]=dd(L,0.0); v[1]=dd(R,0.0); } void addline(double a,double b) { if (empty) { v[0]=dd(L,a*L+b); v[1]=dd(R,a*R+b); empty=false; return; } int i; for (i=sz-1;i>=0;i=i-1) if (v[i].se>a*v[i].fi+b+eps) break; if (i==sz-1) return; if (i<0) { v[0]=dd(L,a*L+b); v[1]=dd(R,a*R+b); sz=2; return; } double a2=(v[i+1].se-v[i].se)/(v[i+1].fi-v[i].fi); double b2=v[i].se-a2*v[i].fi; double x=-(b2-b)/(a2-a); v[i+1]=dd(x,a*x+b); v[i+2]=dd(R,a*R+b); sz=i+3; } double getmax(double x) const { int p=lower_bound(v.begin(),v.begin()+sz,dd(x-eps,x-eps),cmp)-v.begin(); if (p<1) p=1; double a=(v[p].se-v[p-1].se)/(v[p].fi-v[p-1].fi); double b=v[p].se-a*v[p].fi; return (a*x+b); } }; ConvexHull CH; int n,m; void process(void) { scanf("%d",&n); CH=ConvexHull(0.0,INF,n); vector<dd> line; line.push_back(dd(0.0,0.0)); FOR(i,1,n) { int t; scanf("%d",&t); line.push_back(dd(-1.0/i,1.0*t/i)); } sort(line.begin(),line.end()); FORE(it,line) CH.addline(it->fi,it->se); scanf("%d",&m); REP(i,m) { int s; scanf("%d",&s); printf("%.6lf\n",1.0/CH.getmax(s)); } } int main(void) { process(); return 0; }
Comments