Editorial for VM 08 Bài 14 - Đếm tam giác


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<cmath>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;
int m,n,x,y,s,i,j;
unsigned long long r,re;

int main()
{
    cin >> m >> n >> s;
    s*=2;
    fr(x,1,m)
     fr(y,1,n)
     {
        r=0;
        if (x*y==s) r=(x+y)*2;
        else
        {
            fr(i,1,x)
            {
               j=i*y-s;
               if (j%x==0) j/=x;
               if (j<0 || j>y) continue;
               int u=x*y-i*j-(x-i)*j*2-(y-j)*(x-i);
               if (u==s) r+=4;
            }           
        }
        frr(i,x-1,1)
          frr(j,y-1,1)
          {
            int u=x*y*2-i*y-j*x-(x-i)*(y-j);
            if (u>s) break;
            if (u==s) r+=4;
          }
        re+=r*(m-x+1)*(n-y+1);
     }
    cout << re << endl;
    return 0;
}

Code mẫu của ladpro98

program vtri;
uses    math;
const   fi='';
var     x,y,s,t,res,res2,c,i,j:longint;
        factor:array[1..500] of longint;
        inp:text;
procedure input;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,x,y,s);
        close(inp);
end;

procedure init;
begin
        t:=1;
        for i:=1 to s do
        begin
                if s mod i = 0 then begin
                     factor[t]:=i;
                     inc(t);
                end;
        end;
        dec(t);
end;

begin
        input;
        s:=s*2;

        init;
        res:=0;
        res2:=0;
        for i:=0 to x do
        for j:=0 to y do
        for c:=1 to t do
        begin
                if (i+factor[c])<=x then
                begin
                        if j+(s div factor[c]) <=y then
                        begin
                                inc(res,x-1);
                                inc(res2,1);
                        end;
                        if j-(s div factor[c]) >= 0 then
                        begin
                                inc(res,x-1);
                                inc(res2);
                        end;
                end;
                if (i-factor[c])>=0 then
                begin
                        if j+(s div factor[c])<=y then
                        begin
                                inc(res,x-1);
                                inc(res2);
                        end;
                        if j-(s div factor[c])>=0 then begin

                                inc(res,x-1);
                                inc(res2);
                        end;
                end;
                if (j+factor[c])<=y then
                begin


                     if (i+(s div factor[c])<=x) then
                     begin
                        inc(res,y-1);
                        inc(res2);
                     end;
                     if (i-(s div factor[c])>=0) then
                     begin
                        inc(res,y-1);
                        inc(res2);
                     end;
                end;
                if (j-factor[c])>=0 then
                begin
                        if (i+(s div factor[c]))<=x then
                        begin
                                inc(res,y-1);
                                inc(res2);
                        end;
                        if (i-(s div factor[c]))>=0 then
                        begin
                                inc(res,y-1);
                                inc(res2);
                        end;
                end;
        end;
        write((res+res2) div 2);
end.

Code mẫu của RR

{$R+,Q+}
PROGRAM VTRI;
CONST
  FINP='';
  FOUT='';
  esp=0.0001;
VAR
  x,y,s:integer;
  kq:longint;
procedure readInput;
var
  f:text;
begin
  assign(f,FINP); reset(f);
  readln(f,x,y,s);
  close(f);
end;
procedure writeOutput;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
function kc(x1,y1,x2,y2:shortint):real;
begin
  kc:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
function dt(x1,y1,x2,y2,x3,y3:shortint):real;
var
  a,b,c,p:real;
begin
  a:=kc(x1,y1,x2,y2);
  b:=kc(x2,y2,x3,y3);
  c:=kc(x3,y3,x1,y1);
  p:=(a+b+c)/2;
  dt:=sqrt(p*(p-a)*(p-b)*(p-c));
end;
function max(a,b:shortint):shortint;
begin
  if a>b then max:=a else max:=b;
end;
procedure solve;
var
  x1,y1,x2,y2,ym,xm:shortint;
begin
  kq:=0;
  for x1:=-x to x do
  for y1:=0 to y do
  if (x1>0) or (y1>0) then
    for x2:=x1 to x1+x do
    for y2:=0 to y do
    if (x2>x1) or (y2>y1) then
    if (x2-x1<=x) and (x2<=x) then
    if (x2>0) or (y2>0) then
    if abs(dt(x1,y1,x2,y2,0,0)-s)<esp then
      begin
        ym:=max(y1,y2);
        xm:=max(abs(x2-x1),abs(x2));
        xm:=max(xm,abs(x1));
        kq:=kq+(y-ym+1)*(x-xm+1)*2;
      end;
  kq:=kq div 2;
end;
procedure solve1;
var
  x1,y1,x2,y2,x3,y3:shortint;
begin
  for x1:=0 to x do
  for y1:=0 to y do
    for x2:=0 to x do
    for y2:=0 to y do
      for x3:=0 to x do
      for y3:=0 to y do
        if abs(dt(x1,y1,x2,y2,x3,y3)-s)<esp then inc(kq);
  kq:=kq div 6;
end;
BEGIN
  readInput;
  solve;
  writeOutput;
END.

Code mẫu của hieult

#include<stdio.h>
#define mmax(a,b) ((a<b)?(b):(a))
#define mmin(a,b) ((a<b)?(a):(b))
#define myabs(a) ((a<0)?(-a):(a))
int main ()
{
  int w, h, a;
  long long total = 0;
  register int i, j, p, q;
  int k1, dy, k,z;
   scanf (" %d %d %d", &w, &h, &a);
   total=0;
   a=2*a;

      for (i = 0; i <= h; i++)
   for (j = -w; j <= w; j++)
     {
       if (i == 0 && j == 0)
         continue;
       for (p = 0; p <= h; p++)
         {
      k = (( -a) + p * j);
      k1 = ((p * j) +  a);

      z = ((h + 1) - mmax (p, i));

      if (i && j>=0 && (k1%i==0))
        {
          q = k1 / i;
            {
         if (q >= 0 && q <= w )
           {
             if (p == 0 && q == 0)
              goto other;

             total += z*((w + 1) - mmax (j, q));
           }
            }
        }


other:

      if (i && (k%i==0))
        {

          q = k / i;
          if (p == 0 && q == 0)
            continue;
          dy = -mmin (q, j);
          k=mmax(q+dy,j+dy);
            {
         if ( q>=-w&& q <= w)
           {
             if ( k<=w )
               {
            if (p == 0 && (q + dy == 0))
              continue;
            if (i == 0 && (j + dy == 0))
              continue;
            if ( j >= 0 &&  q >= 0)
              continue;
            total += z* ((w + 1) - mmax (k, dy));
               }
           }
            }
        }

         }
     }

      printf ("%lld\n", total);

}

Code mẫu của skyvn97

#include<cstdio>
struct point {
    int x,y;
    point(){}
    point(const int &_x,const int &_y) {
        x=_x;y=_y;  
    }
    bool operator < (const point &a) const {
        if (x<a.x) return (true);
        if (x>a.x) return (false);
        return (y<a.y);
    }
    bool operator > (const point &a) const {
        return (a<*this);
    }
    bool operator == (const point &a) const {
        return (x==a.x && y==a.y);
    }
};
int x,y,s,r;
point a,b,c;
int main(void) {
    scanf("%d",&x);
    scanf("%d",&y);
    scanf("%d",&s);
    r=0;
    for (a.x=0;a.x<=x;a.x++)
        for (a.y=0;a.y<=y;a.y++)
            for (b.x=a.x;b.x<=x;b.x++)
                for (b.y=(a.x==b.x)*(a.y+1);b.y<=y;b.y++)
                    for (c.x=b.x;c.x<=x;c.x++) {
                        if (a.x==b.x) {
                            if (2*s-a.x*b.y+a.y*b.x+c.x*b.y-c.x*a.y==0) r=r+(c.x>b.x)*(y+1)+(c.x==b.x)*(y-c.y);
                            if (-2*s-a.x*b.y+a.y*b.x+c.x*b.y-c.x*a.y==0) r=r+(c.x>b.x)*(y+1)+(c.x==b.x)*(y-c.y);
                        }   
                        else {
                            if ((2*s-a.x*b.y+a.y*b.x+c.x*b.y-c.x*a.y)%(b.x-a.x)==0) {
                                c.y=(2*s-a.x*b.y+a.y*b.x+c.x*b.y-c.x*a.y)/(b.x-a.x);
                                if (b<c && c.y>=0 && c.y<=y) r++;
                            }
                            if ((-2*s-a.x*b.y+a.y*b.x+c.x*b.y-c.x*a.y)%(b.x-a.x)==0) {
                                c.y=(-2*s-a.x*b.y+a.y*b.x+c.x*b.y-c.x*a.y)/(b.x-a.x);
                                if (b<c && c.y>=0 && c.y<=y) r++;
                            }
                        }
                    }
    printf("%d",r);
    return 0;
}

Code mẫu của khuc_tuan

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int s = sc.nextInt();
        long result = 0;
        for (int i = -x; i <= x; ++i)
            for (int j = -y; j <= y; ++j) {
                for (int u = -x; u <= x; ++u)
                    if (i == 0 || (u * j - 2 * s) % i == 0 || (u * j + 2 * s) % i == 0)
                        for (int v = -y; v <= y; ++v) {
                            if (Math.abs(u * j - i * v) == 2 * s) {
                                int minx = Math.min(i, u);
                                minx = Math.min(minx, 0);

                                int maxx = Math.max(i, u);
                                maxx = Math.max(maxx, 0);

                                int miny = Math.min(j, v);
                                miny = Math.min(miny, 0);

                                int maxy = Math.max(j, v);
                                maxy = Math.max(maxy, 0);

                                if (maxx - minx <= x && maxy - miny <= y)
                                    result += (x - (maxx - minx) + 1) * (y - (maxy - miny) + 1);
                            }
                        }
            }
        System.out.println(result / 6);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.