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;

}

Codeforces Round #340(Div.2) (4/5)

poj1654

超客的水墨烟雨

poj3348

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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