Jacquard Circuits.cpp

Jacquard Circuits.cpp

/* 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;
}