Hướng dẫn giải của VOI 05 Bài 4 - Khuôn thép
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 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> #include <climits> #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 RESET(a, v) memset((a), (v), sizeof((a))) #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<int, int> #define X first #define Y second #define VI vector<int> const int N = 2020; const double eps = 1e-7; using namespace std; typedef pair<double, double> point; bool eq(double a, double b) {return fabs(a - b) < eps;} bool eq(point a, point b) {return eq(a.X, b.X) && eq(a.Y, b.Y);} #define sqr(a) ((a) * (a)) double dist(point a, point b) {return sqrt(sqr(a.X - b.X) + sqr(a.Y - b.Y));} struct line { point P, Q; double a, b, c; //aX + bY = c line() {} line(point _P, point _Q) { P = _P; Q = _Q; a = Q.Y - P.Y; b = P.X - Q.X; c = a * P.X + b * P.Y; } }; point cutPoint(line d1, line d2) { double D = d1.a * d2.b - d1.b * d2.a; double Dx = d1.c * d2.b - d1.b * d2.c; double Dy = d1.a * d2.c - d1.c * d2.a; return point(Dx / D, Dy / D); } bool isParallel(line d1, line d2) {return eq(d1.a * d2.b, d1.b * d2.a) && eq(d1.a * d2.c, d1.c * d2.a);} bool inBetween(point a, point b, point c) {return eq(dist(a, b) + dist(b, c), dist(a, c));} //end of helpers int n, m; line edge[N]; point in[N], out[N]; double len(point P, point Q) { //segment [PQ) line PQ (P, Q); FOR(i, 0, n) if (!isParallel(PQ, edge[i])) { point cut = cutPoint(PQ, edge[i]); if (inBetween(edge[i].P, cut, edge[i].Q) && inBetween(cut, Q, P)) return dist(Q, cut); } } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; REP(i, 1, n) cin >> out[i].X >> out[i].Y; out[0] = out[n]; out[n + 1] = out[1]; FOR(i, 0, n) edge[i] = line(out[i], out[i + 1]); cin >> m; REP(i, 1, m) cin >> in[i].X >> in[i].Y; in[0] = in[m]; in[m + 1] = in[1]; double ans = 0; REP(i, 1, m) ans += dist(in[i - 1], in[i]) + min(len(in[i - 1], in[i]), len(in[i + 1], in[i])); cout << setprecision(4) << fixed << ans; return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung const FINP=''; FOUT=''; maxn=2000; type point=record x,y:real; end; var m,n:integer; a,b:array[1..maxn] of point; g1,g2:array[1..maxn] of real; procedure inp; var f:text; i:integer; begin assign(f,FINP); reset(f); readln(f,n); for i:=1 to n do with a[i] do readln(f,x,y); readln(f,m); for i:=1 to m do with b[i] do readln(f,x,y); close(f); end; function min(a,b:real):real; begin if a<b then min:=a else min:=b; end; function kc(a,b:point):real; begin kc:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); end; function f(a,b,c:real;p:point):real; begin f:=a*p.x+b*p.y+c; end; function cat(a,b,c,d:point;var p:point):boolean; var a1,a2,b1,b2,c1,c2,Dx,Dy,Dd:real; begin a1:=b.y-a.y; b1:=a.x-b.x; c1:=a.y*b.x-a.x*b.y; cat:=false; if f(a1,b1,c1,c)*f(a1,b1,c1,d)>0 then exit; a2:=d.y-c.y; b2:=c.x-d.x; c2:=c.y*d.x-c.x*d.y; Dx:=b1*c2-b2*c1; Dy:=c1*a2-c2*a1; Dd:=a1*b2-a2*b1; p.x:=Dx/Dd; p.y:=Dy/Dd; if kc(a,p)<kc(b,p) then exit; cat:=true; end; procedure solve; var i,j,k,ii,jj:integer; p:point; ok:boolean; begin j:=1; for i:=1 to m do begin ok:=false; while not ok do begin if j=n+1 then j:=1; jj:=j+1; if jj=n+1 then jj:=1; ii:=i+1; if ii=m+1 then ii:=1; if cat(b[i],b[ii],a[j],a[jj],p) then begin ok:=true; g1[i]:=kc(p,b[ii]); end else inc(j); end; end; j:=0; for i:=2 to m+1 do begin ok:=false; k:=i; if k=m+1 then k:=1; while not ok do begin inc(j); if j=n+1 then j:=1; jj:=j+1; if jj=n+1 then jj:=1; ii:=k+1; if ii=m+1 then ii:=1; if cat(b[ii],b[k],a[j],a[jj],p) then begin ok:=true; g2[i-1]:=kc(p,b[k]); end; end; end; end; procedure ans; var f:text; kq:real; i,ii:integer; begin assign(f,FOUT); rewrite(f); kq:=0; for i:=1 to m do begin ii:=i+1; if ii=m+1 then ii:=1; kq:=kq+kc(b[i],b[ii]); end; for i:=1 to m do kq:=kq+min(g1[i],g2[i]); writeln(f,kq:0:4); close(f); end; begin inp; solve; ans; end.
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; //typedef long double ld; typedef double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i) #define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i) #define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i) #define Ford(i,a,b) for(__typeof(a) 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)) #define nl puts("") #define sp printf(" ") #define ok puts("ok") //#include <conio.h> 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> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; } 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> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} }; template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); } 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 = 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; } const double PI = 2 * acos(0); const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"}; const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int dr[] = {0, 0, -1, +1}; const int dc[] = {-1, +1, 0, 0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const double eps = ld(1e-9); const ll mod = 100000007; typedef pair<int, int> II; #define maxn 2005 #define maxv 1005 struct Point{ ld x, y; Point() {}; Point(ld _x, ld _y){ x = _x; y = _y; } }; Point O; bool dcmp(ld x, ld y){ return abs(x - y) < eps; } bool dcmpPoint(Point A, Point B){ return dcmp(A.x, B.x) && dcmp(A.y, B.y); } int ccw(Point A, Point B, Point C){ ld dx1 = B.x - A.x, dy1 = B.y - A.y; ld dx2 = C.x - A.x, dy2 = C.y - A.y; ld ret = dx1 * dy2 - dy1 * dx2; if(dcmp(ret, 0)) return 0; return ret < 0 ? -1 : 1; } ld sqrDist(Point P1, Point P2){ return sqr(P1.x - P2.x) + sqr(P1.y - P2.y); } bool nearer(Point P1, Point P2){ return sqrDist(O, P1) < sqrDist(O, P2); } bool cmp(Point P1, Point P2){ int c = ccw(O, P1, P2); if(c != 0) return c > 0; return nearer(P1, P2); } void graham(Point a[], int &n){ if(n < 3) return; int imin = 0; For(i, 1, n - 1) if((a[i].y < a[imin].y) || (a[i].y == a[imin].y && a[i].x < a[imin].x)) imin = i; O = a[imin]; swap(a[0], a[imin]); sort(a + 1, a + n, cmp); int inow = 1; For(i, 2, n - 1){ while(inow > 0 && ccw(a[i], a[inow], a[inow - 1]) >= 0) --inow; ++inow; swap(a[inow], a[i]); } n = inow + 1; } void getLine(Point P0, Point P1, ld &a, ld &b, ld &c){ a = P1.y - P0.y; b = P0.x - P1.x; c = -(a * P0.x + b * P0.y); } bool getIntersect(Point P0, Point P1, Point P2, Point P3, Point &P4){ ld a0, b0, c0, a1, b1, c1; getLine(P0, P1, a0, b0, c0); getLine(P2, P3, a1, b1, c1); ld d = a0 * b1 - a1 * b0; ld dx = b0 * c1 - b1 * c0; ld dy = c0 * a1 - c1 * a0; if(dcmp(d, 0)) return 0; P4 = Point(dx / d, dy / d); return 1; } ld area(Point a[], int n){ ld res = 0; Rep(i, n) res += (a[i].x * a[(i + 1) % n].y - a[i].y * a[(i + 1) % n].x); return abs(res) / 2; } int n, m; Point A[maxn], B[maxn]; vector<double> V[maxn]; double cal(){ double res = 0; Rep(i, m) res += sqrt(sqrDist(B[i], B[(i + 1) % m])); return res; } bool namgiua(Point P0, Point P1, Point P2){ if(dcmpPoint(P0, P2)) return true; if(dcmpPoint(P0, P1)) return false; if(dcmp(P1.x, P2.x)) return (P0.y - P1.y) * (P0.y - P2.y) < 0; return (P0.x - P1.x) * (P0.x - P2.x) < 0; } int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d", &n); Rep(i, n) scanf("%lf %lf", &A[i].x, &A[i].y); scanf("%d", &m); // cout << m << endl; Rep(i, m) scanf("%lf %lf", &B[i].x, &B[i].y); graham(A, n); graham(B, m); double res = cal(); Point P; Rep(i, m){ int j = (i + 1) % m, u, v; for(u = 0; u < n; u++){ v = (u + 1) % n; if(getIntersect(B[i], B[j], A[u], A[v], P) && namgiua(P, A[u], A[v])){ if(sqrDist(B[i], P) < sqrDist(B[j], P)) V[i].pb(sqrt(sqrDist(B[i], P))); else V[j].pb(sqrt(sqrDist(B[j], P))); } } } Rep(i, m){ sort(all(V[i])); res += V[i][0]; } printf("%.4lf\n", res); return 0; }
Bình luận