Pick's theorem says that if a polygon has I vertices/points inside it and B vertices or points on the border of it, then the AREA of this polygon is : AREA = I + ( B / 2 ) -1 There some conditions for applying this theorem. The shape must be a polygon. It can be concave or convex, but not self-intersecting. No circles apply here. Each vertex of the polygon must fall on the board. The polygon must be complete. No holes. Although, if it does have a hole, we can still compute the area by subtracting the smaller area from the larger area if the interior hole is also a lattice polygon. Pick's formula assumes unit measures and unit squares for the area. You can make your unit whatever you desire though if sides of your shape aren't whole numbers. However, you must adjust the value of your unit squares accordingly. So, if you made your lattice units 0.5, your interior squares would each be 0.5*0.5=0.25 square units each. A problem related to Picks Theorem is LightOJ ...
Number of Divisors(NOD) Given N you have to find the number of divisors of N. Solution: Step 1: Generating Prime using Sieve of Eratosthenes Step 2: Count Divisors using prime factorization CODE: long long NOD_using_factorization ( long long n ) /// O(lof2(N)) { long long sqrtn = sqrt ( n ) ; long long tmp = 1 ,divisors = 1 ; for ( int i = 0 ; i < prime. size ( ) && prime [ i ] <= sqrtn ; i ++ ) { ///if ( sieve[n] == 0 ) break; ///*Checks if n is prime or not*/ Please comment This line if n > 1e7 if ( n % prime [ i ] == 0 ) { tmp = 1 ; while ( n % prime [ i ] == 0 ) { n / = prime [ i ] ; tmp ++ ; } divisors * = tmp ; sqrtn = sqrt ( n ) ; ...
Comments
Post a Comment