[World Final 2007][Uva Live Archive] 2395 - Jacquard Circuits

題目網址: http://goo.gl/wT9O6B

題意: 給定一整數點的多邊形，求與此多邊形的形狀相同的最小多邊形及其M倍以內的多邊形內部所包含的整數點點數總和。



解法: 須先刪除共線的點，然後將多邊形的一頂點平移至原點，接著求出所有邊的x變量、y變量的最大公因數D，接著將所有座標除以D後即得到最小相似多邊形，接著可以皮克定理(Pick's Theorem) A = i + B/2 - 1 ，A為多邊形的面積，i為多邊行內部整數點點數，B為多邊形邊上點數，可應用此定理推出答案之公式，ans = S1*(m*(m+1)*(2m+1)/6) - (B/2)*(m*(m+1)/2) + m。

TAG: Computational Geometry

注意: 這題的測資非常的坑人，答案會趨近於2^64-1，所以最後算出來的答案非常容易爆炸，需要配合unsigned long long及long long使用。

程式碼:

	/* Author: Cheng-Shih Wong
	* Prob. name: Jacquard Circuits
	* Prob. source: World Final 2007
	* Prob. URL: http://goo.gl/wT9O6B
	* Prob. catogory: Computaional Geometry
	* Date: 2014/05/18
	*/
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <vector>
	using namespace std;
	typedef unsigned long long ULL;
	typedef long long LL;
	LL ABS( LL x ) { return (x<0 ? -x:x); }
	struct Point {
	int x, y;
	Point( int _x = 0, int _y = 0 ):
	x(_x), y(_y) {}
	const Point operator-( const Point &op ) const {
	return Point( x-op.x, y-op.y );
	}
	const LL operator^( const Point &op ) const {
	return ((LL)x*op.y-(LL)y*op.x);
	}
	};
	typedef vector<Point> Polygon;
	int n;
	ULL m;
	Polygon polygon;
	Point pn[1005];
	ULL B;
	int ti = 1;
	const LL polygonArea( const Polygon &p )
	{
	int i, s = p.size();
	ULL ret = 0LL;
	for( i = 0; i < s; ++i ) ret += p[i]^p[(i+1)%s];
	return ABS(ret);
	}
	int gcd( int a, int b )
	{
	return (!b ? a:gcd(b,a%b));
	}
	void init( void )
	{
	static int i, ldPoint, vn, d;
	static Point tmpp;
	for( i = 0; i < n; ++i ) scanf( "%d%d", &pn[i].x, &pn[i].y );
	ldPoint = 0;
	for( i = 1; i < n; ++i )
	if( pn[i].y < pn[ldPoint].y || (pn[i].y==pn[ldPoint].y && pn[i].x<pn[ldPoint].x) ) ldPoint = i;
	polygon.clear();
	polygon.push_back(pn[ldPoint]);
	polygon.push_back(pn[(ldPoint+1)%n]);
	for( i = 2; i < n; ++i ) {
	vn = polygon.size();
	if( ((polygon[vn-1]-polygon[vn-2])^(pn[(i+ldPoint)%n]-polygon[vn-1])) == 0 ) polygon.pop_back();
	polygon.push_back( pn[(i+ldPoint)%n]);
	}
	vn = polygon.size();
	if( ((polygon[vn-1]-polygon[vn-2])^(pn[ldPoint]-polygon[vn-1])) == 0 ) polygon.pop_back();
	n = polygon.size();
	for( i = 1; i < n; ++i ) polygon[i] = polygon[i]-polygon[0];
	polygon[0] = Point();
	for( i = 1; i < n; ++i ) {
	if( polygon[i].x ) d = polygon[i].x;
	if( polygon[i].y ) d = polygon[i].y;
	}
	for( i = 1; i < n; ++i ) {
	d = gcd( d, polygon[i].x );
	d = gcd( d, polygon[i].y );
	}
	for( i = 1; i < n; ++i ) {
	polygon[i].x /= d; polygon[i].y /= d;
	}
	}
	void solve( void )
	{
	static int i;
	static Point tmpp;
	static ULL ans;
	B = 0ULL;
	for( i = 0; i < n; ++i ) {
	tmpp = polygon[(i+1)%n]-polygon[i];
	if( !tmpp.x || !tmpp.y ) B += ABS(tmpp.x)+ABS(tmpp.y);
	else B += gcd( ABS(tmpp.x), ABS(tmpp.y) );
	}
	ans = (polygonArea(polygon)*((((m*(m+1))/2)*(2*m+1))/3))/2-(B*m*(m+1))/4+m;
	printf( "Case %d: %llu\n", ti++, ans );
	}
	int main( void )
	{
	//freopen( "p2395.in", "r", stdin );
	while( scanf( "%d%llu", &n, &m ) == 2 && (n||m) ) {
	init();
	solve();
	}
	return 0;
	}

view raw Jacquard Circuits.cpp hosted with ❤ by GitHub