Hướng dẫn giải của VM 08 Bài 14 - Đếm tam giác


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.

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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.