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.
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