Integral Points Inside Triangle GFG POTD 20-06-2024 solved
Vložit
- čas přidán 18. 06. 2024
- Code:
class Solution {
public:
long long gcd(long long a,long long b){
if(b==0)return a;
return gcd(b,a%b);
}
long long bound_pts(long long x1,long long y1,long long x2,long long y2){
if(x1==x2){return abs(y1-y2)-1;}
if(y1==y2){return abs(x1-x2)-1;}
return gcd(abs(x1-x2),abs(y1-y2))-1;
}
long long int InternalCount(long long int p[], long long int q[],
long long int r[]) {
long long bound = bound_pts(p[0],p[1],q[0],q[1])+bound_pts(p[0],p[1],r[0],r[1])+
bound_pts(q[0],q[1],r[0],r[1])+3;
long long area = abs(p[0]*(q[1]-r[1])+ q[0]*(r[1]-p[1])+r[0]*(p[1]-q[1]));
return (area - bound+2)/2;
}
};