Editorial for Bộ ba điểm thẳng hàng


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.

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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.