28 | 1月 | 2016 | 超客的水墨烟雨

poj2954

28 1月 2016

Triangle

A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle (which happen to be lattice points), you are to count the number of lattice points which lie completely inside of the triangle (points on the edges or vertices of the triangle do not count).

Input

The input test file will contain multiple test cases. Each input test case consists of six integers x₁, y₁, x₂, y₂, x₃, and y₃, where (x₁, y₁), (x₂, y₂), and (x₃, y₃) are the coordinates of vertices of the triangle. All triangles in the input will be non-degenerate (will have positive area), and −15000 ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 15000. The end-of-file is marked by a test case with x₁ = y₁ = x₂= y₂ = x₃ = y₃ = 0 and should not be processed.

Output

For each input case, the program should print the number of internal lattice points on a single line.

Sample Input

0 0 1 0 0 1
0 0 5 0 0 5
0 0 0 0 0 0

Sample Output

Source

Stanford Local 2004

题目类型：格点多边形(pick定理)

算法分析：由pick定理可知，格点多边形内部的格点数为：b = (res * 2 - a + 2) / 2。res * 2可以用叉乘计算，a可以用gcd计算

/*************************************************
Author        :supermaker
Created Time  :2016/1/28 15:05:47
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

struct Point
{
	LL x, y;
	Point () {}
	Point (LL xx, LL yy) : x (xx), y (yy) {}
	
	Point operator - (const Point &a) const
	{
		return Point (x - a.x, y - a.y);
	}

	LL operator ^ (const Point &a) const
	{
		return x * a.y - y * a.x;
	}

	LL operator * (const Point &a) const
	{
		return x * a.x + y * a.y;
	}
};

Point p[6];

LL mabs (LL val)
{
	if (val < 0) return -val;
	return val;
}

LL gcd (LL a, LL b)
{
	if (b == 0) return a;
	else return gcd (b, a % b);
}

int main()
{
    //CFF;
    //CPPFF;    
	while (1)
	{
		bool is_zero = true;
		for (int i = 0; i < 3; i++)
		{
			scanf ("%lld%lld", &p[i].x, &p[i].y);
			if (p[i].x != 0 || p[i].y != 0)
				is_zero = false;
		}

		if (is_zero) break;

		LL res = 0, cnta = 0;
		for (int i = 0; i < 3; i++)
		{
			res += p[i] ^ p[(i+1)%3];
			cnta += gcd (mabs (p[i].x - p[(i+1)%3].x), mabs (p[i].y - p[(i+1)%3].y));
		}
		res = mabs (res);
		printf ("%lld\n", (res - cnta + 2) / 2);
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

/*************************************************

Author :supermaker

Created Time :2016/1/28 15:05:47

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

struct Point

{

LL x, y;

Point () {}

Point (LL xx, LL yy) : x (xx), y (yy) {}

Point operator - (const Point &a) const

{

return Point (x - a.x, y - a.y);

}

LL operator ^ (const Point &a) const

{

return x * a.y - y * a.x;

}

LL operator * (const Point &a) const

{

return x * a.x + y * a.y;

}

};

Point p[6];

LL mabs (LL val)

{

if (val < 0) return -val;

return val;

}

LL gcd (LL a, LL b)

{

if (b == 0) return a;

else return gcd (b, a % b);

}

int main()

{

//CFF;

//CPPFF;

while (1)

{

bool is_zero = true;

for (int i = 0; i < 3; i++)

{

scanf ("%lld%lld", &p[i].x, &p[i].y);

if (p[i].x != 0 || p[i].y != 0)

is_zero = false;

}

if (is_zero) break;

LL res = 0, cnta = 0;

for (int i = 0; i < 3; i++)

{

res += p[i] ^ p[(i+1)%3];

cnta += gcd (mabs (p[i].x - p[(i+1)%3].x), mabs (p[i].y - p[(i+1)%3].y));

}

res = mabs (res);

printf ("%lld\n", (res - cnta + 2) / 2);

}

return 0;

}

poj1265

maksyuki 发表于 oj 分类，标签: 计算几何-点线面\点积\叉积

28 1月 2016

Area

Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new research and development facility the company has installed 阅读全文 »

poj1654

maksyuki 发表于 oj 分类，标签: 计算几何-点线面\点积\叉积

28 1月 2016

Area

You are going to compute the area of a special kind of polygon. One vertex of the polygon is the origin of the orthogonal coordinate system. From this vertex, you may go step by step to the following vertexes of the polygon until back to the initial vertex. For each step you may go North, West, South or East with step length of 1 unit, or go Northwest, Northeast, Southwest or Southeast with step length of square root of 2.

For example, this is a legal polygon to be computed and its area is 2.5:

Input

The first line of input is an integer t (1 <= t <= 20), the number of the test polygons. Each of the following lines contains a string composed of digits 1-9 describing how the polygon is formed by walking from the origin. Here 8, 2, 6 and 4 represent North, South, East and West, while 9, 7, 3 and 1 denote Northeast, Northwest, Southeast and Southwest respectively. Number 5 only appears at the end of the sequence indicating the stop of walking. You may assume that the input polygon is valid which means that the endpoint is always the start point and the sides of the polygon are not cross to each other.Each line may contain up to 1000000 digits.

Output

For each polygon, print its area on a single line.

Sample Input

4
5
825
6725
6244865

Sample Output

0.5

Source

POJ Monthly--2004.05.15 Liu Rujia@POJ

题目类型：多边形面积

算法分析：由于这道题没有SPJ，所以要使用long long来运算，否则使用double会出现精度误差！！！注意最后输出的时候若结果是整数就输出整数，否则输出小数！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/28 11:12:15
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e6 + 66;

const int dx[] = {-6, 1, 1, 1, 0, -6, 0, -1, -1, -1};
const int dy[] = {-6, -1, 0, 1, -1, -6, 1, -1, 0, 1};

struct Point
{
	LL x, y;
	Point () {}
	Point (LL xx, LL yy) : x (xx), y (yy) {}

	Point operator - (const Point &a) const
	{
		return Point (x - a.x, y - a.y);
	}

	LL operator ^ (const Point &a) const
	{
		return x * a.y - y * a.x; 
	}

	LL operator * (const Point &a) const
	{
		return x * a.x + y * a.y;
	}
};

char s[maxn];
int n;

int main()
{
    //CFF;
    //CPPFF;
	int t;
	scanf ("%d", &t);
	while (t--)
	{
		scanf (" %s", s);
		n = strlen (s);
		LL px = 0, py = 0;
		Point p1 = Point (px, py), p2;
		LL res = 0;
		for (int i = 0; i < n - 1; i++)
		{
			int pos = s[i] - '0';
			px = px + dx[pos], py = py + dy[pos];
			p2 = Point (px, py);
			res += (p1 ^ p2);
			p1 = p2;
		}
		if (res < 0) res = -res;
		//res = abs (res);
		if (res & 1)
			printf ("%lld.5\n", res / 2);

		else
			printf ("%lld\n", res / 2);
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

/*************************************************

Author :supermaker

Created Time :2016/1/28 11:12:15

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e6 + 66;

const int dx[] = {-6, 1, 1, 1, 0, -6, 0, -1, -1, -1};

const int dy[] = {-6, -1, 0, 1, -1, -6, 1, -1, 0, 1};

struct Point

{

LL x, y;

Point () {}

Point (LL xx, LL yy) : x (xx), y (yy) {}

Point operator - (const Point &a) const

{

return Point (x - a.x, y - a.y);

}

LL operator ^ (const Point &a) const

{

return x * a.y - y * a.x;

}

LL operator * (const Point &a) const

{

return x * a.x + y * a.y;

}

};

char s[maxn];

int n;

int main()

{

//CFF;

//CPPFF;

int t;

scanf ("%d", &t);

while (t--)

{

scanf (" %s", s);

n = strlen (s);

LL px = 0, py = 0;

Point p1 = Point (px, py), p2;

LL res = 0;

for (int i = 0; i < n - 1; i++)

{

int pos = s[i] - '0';

px = px + dx[pos], py = py + dy[pos];

p2 = Point (px, py);

res += (p1 ^ p2);

p1 = p2;

}

if (res < 0) res = -res;

//res = abs (res);

if (res & 1)

printf ("%lld.5\n", res / 2);

else

printf ("%lld\n", res / 2);

}

return 0;

}

poj3348

maksyuki 发表于 oj 分类，标签: 计算几何-凸包

28 1月 2016

Cows

However, because you will oversee the construction of the pasture yourself, all the farmers want to know is how many cows they can put in the pasture. It is well known that a cow needs at least 50 square metres of pasture to survive.Your friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Given the locations of some trees, you are to help farmers try to create the largest pasture that is possible. Not all the trees will need to be used.

Input

The first line of input contains a single integer, n (1 ≤ n ≤ 10000), containing the number of trees that grow on the available land. The next n lines contain the integer coordinates of each tree given as two integers x and y separated by one space (where -1000 ≤ x, y ≤ 1000). The integer coordinates correlate exactly to distance in metres (e.g., the distance between coordinate (10; 11) and (11; 11) is one metre).

Output

You are to output a single integer value, the number of cows that can survive on the largest field you can construct using the available trees.

Sample Input

4
0 0
0 101
75 0
75 101

Sample Output

151

Source

CCC 2007

题目类型：凸包+多边形面积

算法分析：先使用Garham求出凸包，然后求凸包的面积

/*************************************************
Author        :supermaker
Created Time  :2016/1/28 10:33:53
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e4 + 66;

int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1;
}

struct Point
{
	double x, y;
	Point () {}
	Point (double xx, double yy) : x (xx), y (yy) {}

	Point operator - (const Point &a) const
	{
		return Point (x - a.x, y - a.y);
	}

	double operator ^ (const Point &a) const
	{
		return x * a.y - y * a.x;
	}

	double operator * (const Point &a) const
	{
		return x * a.x + y * a.y;
	}
};


Point p[maxn], pp[maxn];
int n, len;
stack <int> sta;

double Dist (Point p1, Point p2)
{
	return sqrt ((p2 - p1) * (p2 - p1));
}

bool polarcmp (Point p1, Point p2)
{
	double tt = (p1 - p[1]) ^ (p2 - p[1]);
	if (sgn (tt) == 1) return true;
	else if (sgn (tt) == 0 && sgn (Dist (p1, p[1]) - Dist (p2, p[1])) <= 0) return true;
	return false;
}

void Garham ()
{
	Point start = p[1];
	int start_pos = 1;
	for (int i = 1; i <= n; i++)
		if (sgn (p[i].x - start.x) == -1 || (sgn (p[i].x - start.x) == 0 && sgn (p[i].y - start.y) == -1))
			start = p[i], start_pos = i;
	swap (p[start_pos], p[1]);
	sort (p + 2, p + n + 1, polarcmp);

	while (!sta.empty ()) sta.pop ();
	if (n == 1) sta.push (1);
	else if (n == 2) sta.push (1), sta.push (2);
	else
	{
		sta.push (1), sta.push (2);
		for (int i = 3; i <= n; i++)
		{
			while (sta.size () >= 2)
			{
				int tt1 = sta.top (); sta.pop ();
				int tt2 = sta.top (); sta.pop ();
				if (sgn ((p[tt1] - p[tt2]) ^ (p[i] - p[tt2])) <= 0)
					sta.push (tt2);

				else
				{
					sta.push (tt2), sta.push (tt1);
					break;
				}
			}
			sta.push (i);
		}
	}
}

double Calc ()
{
	double res = 0;
	for (int i = 0; i < len; i++)
		res += (pp[i] ^ pp[(i+1)%len]) / 2.0;
	return fabs (res);
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf ("%lf%lf", &p[i].x, &p[i].y);

		Garham ();
		len = 0; 
		while (!sta.empty ())
		{
			int cur = sta.top (); sta.pop ();
			pp[len++] = p[cur];
		}
		printf ("%d\n", (int) (Calc () / 50.0)); 
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

/*************************************************

Author :supermaker

Created Time :2016/1/28 10:33:53

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e4 + 66;

int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

struct Point

{

double x, y;

Point () {}

Point (double xx, double yy) : x (xx), y (yy) {}

Point operator - (const Point &a) const

{

return Point (x - a.x, y - a.y);

}

double operator ^ (const Point &a) const

{

return x * a.y - y * a.x;

}

double operator * (const Point &a) const

{

return x * a.x + y * a.y;

}

};

Point p[maxn], pp[maxn];

int n, len;

stack <int> sta;

double Dist (Point p1, Point p2)

{

return sqrt ((p2 - p1) * (p2 - p1));

}

bool polarcmp (Point p1, Point p2)

{

double tt = (p1 - p[1]) ^ (p2 - p[1]);

if (sgn (tt) == 1) return true;

else if (sgn (tt) == 0 && sgn (Dist (p1, p[1]) - Dist (p2, p[1])) <= 0) return true;

return false;

}

void Garham ()

{

Point start = p[1];

int start_pos = 1;

for (int i = 1; i <= n; i++)

if (sgn (p[i].x - start.x) == -1 || (sgn (p[i].x - start.x) == 0 && sgn (p[i].y - start.y) == -1))

start = p[i], start_pos = i;

swap (p[start_pos], p[1]);

sort (p + 2, p + n + 1, polarcmp);

while (!sta.empty ()) sta.pop ();

if (n == 1) sta.push (1);

else if (n == 2) sta.push (1), sta.push (2);

else

{

sta.push (1), sta.push (2);

for (int i = 3; i <= n; i++)

{

while (sta.size () >= 2)

{

int tt1 = sta.top (); sta.pop ();

int tt2 = sta.top (); sta.pop ();

if (sgn ((p[tt1] - p[tt2]) ^ (p[i] - p[tt2])) <= 0)

sta.push (tt2);

else

{

sta.push (tt2), sta.push (tt1);

break;

}

sta.push (i);

}

double Calc ()

{

double res = 0;

for (int i = 0; i < len; i++)

res += (pp[i] ^ pp[(i+1)%len]) / 2.0;

return fabs (res);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d", &n) != EOF)

{

for (int i = 1; i <= n; i++)

scanf ("%lf%lf", &p[i].x, &p[i].y);

Garham ();

len = 0;

while (!sta.empty ())

{

int cur = sta.top (); sta.pop ();

pp[len++] = p[cur];

}

printf ("%d\n", (int) (Calc () / 50.0));

}

return 0;

}

超客的水墨烟雨

poj2954

poj1265

poj1654

poj3348

分类目录

标签云

书签

近期评论

2016年1月
一	二	三	四	五	六	日
« 12月				2月 »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31