Hướng dẫn giải của Bộ ba điểm thẳng hàng
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 <cstdio> #include <utility> using namespace std; int n,re,m,a[2020],b[2020]; pair<int,int> c[2020]; bool cmp(pair<int,int> i,pair<int,int> j) { return i.second*j.first<i.first*j.second; } int main() { int n,x,y; cin >> n; for (int i=0;i<n;i++) cin >> a[i] >> b[i]; for (int i=0;i<n;i++) { m=0; for (int j=0;j<n;j++) { x=a[j]-a[i]; y=b[j]-b[i]; if (y<0 || (y==0 && x<=0)) continue; c[m++]=make_pair(x,y); } if (!m) continue; sort(c,c+m,cmp); int cur=1; for (int i=1;i<m;i++) if (!cmp(c[i],c[i-1]) && !cmp(c[i-1],c[i])) re+=cur++; else cur=1; } cout << re << endl; }
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; #define N 2000 long long sqr(const int &x) { return (long long) x * x; } struct Point { int x, y; void read() { scanf("%d%d", &x, &y); } } p[N]; struct Vector { int x, y; Vector() {} Vector(const Point &A, const Point &B) { int tx = B.x - A.x, ty = B.y - A.y; if(ty < 0 || ty == 0 && tx < 0) { ty = -ty; tx = -tx; } x = tx; y = ty; } inline bool operator < (const Vector &o) const { return x * o.y - y * o.x > 0; } inline bool operator == (const Vector &o) const { return x * o.y == y * o.x; } inline bool operator != (const Vector &o) const { return x * o.y != y * o.x; } } u[N]; int main() { #ifdef __DONGOCKHANH__ freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); for(int i = 0; i < n; p[i++].read()); int res = 0; for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) u[j] = Vector(p[i], p[j]); sort(u+i+1, u+n); int begin = i+1; for(int j = i + 1; j < n; ++j) if(u[j] != u[begin]) { res += (j - begin) * (j - begin - 1) / 2; begin = j; } res += (n - begin) * (n - begin - 1) / 2; } printf("%d\n", res); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define X first #define Y second const int N = 2002; using namespace std; int n, res; ii vt[N], a[N]; ii reduce(int x, int y) { //toi gian vector (x, y) int g = __gcd(x, y); x /= g; y /= g; if (x < 0) {x = -x; y = -y;} return ii(x, y); } int main() { scanf("%d", &n); int i, j, k, m; for(i = 1; i <= n; i++) scanf("%d %d", &a[i].X, &a[i].Y); for(i = 1; i < n; i++) { m = 0; for(j = i + 1; j <= n; j++) vt[m++] = reduce(a[i].X - a[j].X, a[i].Y - a[j].Y); sort(vt, vt + m); for(j = 0; j < m; j = k) { k = j; while (k < m && vt[k] == vt[j]) k++; res += (k - j) * (k - j - 1) / 2; } } printf("%d", res); return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions {$R+,Q+} const FINP=''; FOUT=''; eps=1e-10; oo=1000000; MAXN=2000; var x,y:array[1..MAXN] of longint; tan:array[1..MAXN] of double; n,sl,kq:longint; procedure inp; inline; var f:text; i:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do read(f,x[i],y[i]); close(f); end; procedure swap(var a,b:double); inline; var temp:double; begin temp:=a; a:=b; b:=temp; end; procedure sort(l,r:longint); inline; var i,j:longint; mid,tg:double; begin i:=l; j:=r; mid:=tan[(l+r) div 2]; repeat while (tan[i]<mid) do inc(i); while (tan[j]>mid) do dec(j); if i<=j then begin swap(tan[i],tan[j]); inc(i); dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure find(u:longint); inline; var v,i,count:longint; begin sl:=0; for v:=u+1 to n do begin inc(sl); if (x[u]=x[v]) then tan[sl]:=oo else if (y[u]=y[v]) then tan[sl]:=0 else tan[sl]:=(y[v]-y[u])/(x[v]-x[u]); end; if sl=0 then exit; sort(1,sl); count:=1; for i:=2 to sl do begin if abs(tan[i]-tan[i-1])<eps then inc(count) else begin kq:=kq+(count*(count-1)) shr 1; count:=1; end; end; kq:=kq+(count*(count-1)) shr 1; end; procedure solve; inline; var i,j:longint; begin kq:=0; for i:=1 to n do find(i); end; procedure ans; inline; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,kq); close(f); end; begin inp; solve; ans; end.
Code mẫu của hieult
#include <cstdio> #include <algorithm> #include <iostream> //#include <conio.h> using namespace std; struct diem{ int x,y; }; struct vt{ int x,y; vt(){x = 0;y =0;} vt(int a,int b){ x = a; y = b; if(x == 0) y = abs(y); if(x < 0){ x = -x; y = -y; } } bool operator < (vt V) const{ return x * V.y < y * V.x; } }; int main() { // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); int test,n,so; long long kq,run; diem A[2222]; vt V[2222]; // scanf("%d",&test); //for(int itest = 0;itest<test;itest++){ scanf("%d",&n); for(int i = 0;i<n;i++) scanf("%d %d",&A[i].x,&A[i].y); kq = 0; so = 0; for(int i = 0;i<n-1;i++){ run = 0; for(int j = i+1;j<n;j++) V[j-i-1] = vt(A[j].x-A[i].x,A[j].y-A[i].y); sort(V, V + n - i - 1); for(int j = 0; j<n-i-2;j++){ if(!(V[j] < V[j + 1])){ run++; } else{ run = 0; } kq+=run; } // printf("%d %d\n",i,kq); // printf("1"); } printf("%lld",kq); //} //getch(); }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; struct Point { int x, y; }; struct Frac { int a, b; }; int n, nf; Point a[2020]; Frac f[2020]; bool cmp(Frac a, Frac b) { return a.a*b.b < a.b*b.a; } int main() { scanf("%d", &n); for(int i=0;i<n;++i) scanf("%d%d", &a[i].x, &a[i].y); unsigned int total = 0; for(int i=0;i<n;++i) { Point p = a[i]; int ngang = 0; nf = 0; for(int j=i+1;j<n;++j) if(i!=j) { if(a[j].y==p.y) ++ ngang; // else if(a[j].x==p.x) ++ doc; else { int dy = a[j].y - p.y; int dx = a[j].x - p.x; if(dy<0) { dy = -dy; dx = -dx; } f[nf].a = dx; f[nf].b = dy; ++nf; } } total += ngang * (ngang-1) / 2; sort(f,f+nf,cmp); int c = 0; for(int j=0;j<nf;++j) if(j==0) c = 1; else if(f[j].a*f[j-1].b==f[j].b*f[j-1].a) ++c; else { total += c * (c-1) / 2; c = 1; } total += c * (c-1) / 2; } cout << total << endl; return 0; }
Bình luận