Hướng dẫn giải của Hình chữ nhật
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 flashmt
#include<iostream> #include<algorithm> #include<vector> #include<utility> #define fr(a,b,c) for (a=b;a<=c;a++) #define pii pair<int,int> #define pb push_back #define mp make_pair #define F first #define S second using namespace std; int n; vector< pii > a,b,c; long long re; bool cmp(pii i,pii j) { return 1.0*i.F/i.S<1.0*j.F/j.S; } bool cmpp(pii i,pii j) { return 1.0*i.S/i.F>1.0*j.S/j.F; } long long area(pii q,pii u,pii t) { long long s=-1LL*q.S*q.F+1LL*(q.S+u.S)*(q.F-u.F)+1LL*(u.S+t.S)*(u.F-t.F)+1LL*t.S*t.F; if (s<0) s=-s; return s/2; } int main() { int i,x,y,ib,ic,k,j,z; cin >> n; fr(i,1,n) cin >> x >> y, a.pb(mp(x,y)); sort(a.begin(),a.end()); fr(i,0,n-1) { b.clear(); c.clear(); fr(j,0,n-1) { if (j==i) continue; if ((a[j].S>a[i].S && a[j].F>=a[i].F) || (a[j].S<a[i].S && a[j].F<=a[i].F)) b.pb(mp(a[j].F-a[i].F,a[j].S-a[i].S)); else c.pb(mp(a[j].F-a[i].F,a[j].S-a[i].S)); } if (b.empty() || c.empty()) continue; sort(b.begin(),b.end(),cmp); sort(c.begin(),c.end(),cmpp); ib=0; ic=0; while (ib<b.size() && ic<c.size()) { j=ib+1; while (j<b.size() && 1.0*b[j].F/b[j].S==1.0*b[ib].F/b[ib].S) j++; while (ic<c.size() && 1.0*b[ib].F/b[ib].S>-1.0*c[ic].S/c[ic].F) ic++; if (ic>=c.size()) break; while (ic<c.size() && 1.0*b[ib].F/b[ib].S==-1.0*c[ic].S/c[ic].F) { fr(k,ib,j-1) { x=b[k].F+c[ic].F+a[i].F; y=b[k].S+c[ic].S+a[i].S; z=lower_bound(a.begin(),a.end(),mp(x,y))-a.begin(); if (z<n && a[z].F==x && a[z].S==y) re=max(re,area(c[ic],mp(x-a[i].F,y-a[i].S),b[k])); } ic++; } ib=j; } } cout << re << endl; return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define X first #define Y second const int N = 2000; using namespace std; typedef pair<long long, long long> II; int n, m; II a[N]; long long dist(II &a, II &b) { return (a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y); } long long area(II &a, II &b, II &c) { return abs(a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y)); } struct diag { II center; long long dist; II index; diag() {} diag(II _c, long long d, II id) { center = _c; dist = d; index = id; } bool operator < (const diag &that) const { if (center != that.center) return center < that.center; if (dist != that.dist) return dist < that.dist; return index < that.index; } bool operator == (const diag &that) const { return center == that.center && dist == that.dist; } } b[N * N >> 1]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) cin >> a[i].X >> a[i].Y; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) b[m++] = diag(II(a[i].X + a[j].X, a[i].Y + a[j].Y), dist(a[i], a[j]), II(i, j)); sort(b, b + m); long long ans = 0; for (int i = 0, j; i < m; i = j + 1) { j = i; while (j + 1 < m && b[i] == b[j + 1]) ++j; for (int l = i; l <= j; ++l) for (int r = l + 1; r <= j; ++r) ans = max(ans, area(a[b[l].index.X], a[b[r].index.X], a[b[l].index.Y]) + area(a[b[l].index.X], a[b[r].index.Y], a[b[l].index.Y])); } cout << ans / 2 << endl; return 0; }
Code mẫu của RR
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair using namespace std; const double PI = acos(-1.0); typedef pair<ll, ll> Point; int n; Point a[1511]; pair<Point, pair<ll,pair<int,int> > > seg[1511*1511]; Point mid(const Point &a, const Point &b) { Point res; res.F = (a.F + b.F) / 2; res.S = (a.S + b.S) / 2; return res; } #define sqr(x) ((x)*(x)) ll len(const Point &a, const Point &b) { return sqr(a.F - b.F) + sqr(a.S - b.S); } ll ccw(const Point &a, const Point &b, const Point &c) { return abs((c.S - b.S) * (a.F - b.F) - (c.F - b.F) * (a.S - b.S)); } //Buffer reading int INP,AM; #define BUFSIZE (1<<10) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ fread(BUF,1,BUFSIZE,stdin); \ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); GN(n); FOR(i,1,n) { GN(a[i].F); GN(a[i].S); a[i].F *= 2; a[i].S *= 2; } int now = 0; FOR(i,1,n) FOR(j,i+1,n) { seg[now++] = MP(mid(a[i], a[j]), MP(len(a[i], a[j]), MP(i,j))); } sort(seg, seg+now); FOR(i,1,n) { a[i].F /= 2; a[i].S /= 2; } long long res = 0; REP(i,now) FOR(j,i+1,now-1) if (seg[i].F == seg[j].F && seg[i].S.F == seg[j].S.F) { int u = seg[i].S.S.F, v = seg[j].S.S.F, w = seg[i].S.S.S; res = max(res, ccw(a[u], a[v], a[w])); } else break; cout << res << endl; return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.2 #define maxn 1502 #define oo 1111111111 #define base 100000000 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; struct diem{ long long x,y; }; struct vec_tor{ long long x,y,dai; double goc; vec_tor(){}; vec_tor(diem D1,diem D2){ x = D1.x+D2.x; y = D1.y+D2.y; dai = (D1.y-D2.y)*(D1.y-D2.y) +(D1.x-D2.x)*(D1.x-D2.x); goc = atan2(D2.y-D1.y,D2.x-D1.x); } bool operator <(vec_tor T)const{ if(x!=T.x) return x<T.x; if(y!=T.y) return y<T.y; if(dai!=T.dai) return dai<T.dai; return goc<T.goc; } bool operator ==(vec_tor T)const{ return (x == T.x && y == T.y && dai == T.dai); } }; long long dientich(vec_tor V1, vec_tor V2){ double KQ = V1.dai*sin(V1.goc-V2.goc)/2.0; return (long long)(KQ+ep); } vec_tor A[maxn*maxn]; diem a[maxn]; int n,m; vector<vec_tor> V; long long KQ = 0; int main(){ //freopen("REC04.in","r",stdin); int run = 0; scanf("%d",&n); for(int i = 1;i<=n;i++){ scanf("%lld %lld",&a[i].x,&a[i].y); for(int j = 1;j<i;j++){ A[run++] = vec_tor(a[j],a[i]); } } sort(A,A+run); V.resize(run); //for(int i = 0;i<run;i++) printf("%d %lld %lld %lld %.2lf\n",i,A[i].x,A[i].y,A[i].dai,A[i].goc); int u = 0,v; while(u<run){ v = u; V.clear(); //printf("%d\n",u); //getch(); while(A[v]==A[u]){ //if(v==12) printf("?\n"); V.push_back(A[v]); // if(v==12) printf("?\n"); v++; // printf("%d\n",v); } u = v; v = 0; m = V.size(); //printf("%d\n",m); for(int i = 0;i<m;i++){ V[i+m] = V[i]; V[i+m].goc = V[i].goc+2*PI; } for(int i = 0;i<m;i++){ while(V[v].goc-V[i].goc<PI/2) v++; KQ >?= dientich(V[v],V[i]); KQ >?= dientich(V[v-1],V[i]); } } printf("%lld\n",KQ); // getch(); }
Bình luận