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

poj2139

maksyuki 发表于 oj 分类，标签: 图论-最短路

31 1月 2016

Six Degrees of Cowvin Bacon

The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon".

The game works like this: each cow is considered to 阅读全文 »

poj2449

maksyuki 发表于 oj 分类，标签: 图论-次\k短路

31 1月 2016

Remmarguts' Date

"Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little ducks' head, he told them a story. 阅读全文 »

poj1066

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

30 1月 2016

Treasure Hunt

Archeologists from the Antiquities and Curios Museum (ACM) have flown to Egypt to examine the great pyramid of Key-Ops. Using state-of-the-art technology they are able to determine that the lower floor of the pyramid is constructed from a series of straightline walls, which intersect to form numerous enclosed chambers. Currently, no doors exist to allow access to any chamber. This state-of-the-art technology has also pinpointed the location of the treasure room. What these dedicated (and greedy) archeologists want to do is blast doors through the walls to get to the treasure room. However, to minimize the damage to the artwork in the intervening chambers (and stay under their government grant for dynamite) they want to blast through the minimum number of doors. For structural integrity purposes, doors should only be blasted at the midpoint of the wall of the room being entered. You are to write a program which determines this minimum number of doors.
An example is shown below:

Input

The input will consist of one case. The first line will be an integer n (0 <= n <= 30) specifying number of interior walls, followed by n lines containing integer endpoints of each wall x1 y1 x2 y2 . The 4 enclosing walls of the pyramid have fixed endpoints at (0,0); (0,100); (100,100) and (100,0) and are not included in the list of walls. The interior walls always span from one exterior wall to another exterior wall and are arranged such that no more than two walls intersect at any point. You may assume that no two given walls coincide. After the listing of the interior walls there will be one final line containing the floating point coordinates of the treasure in the treasure room (guaranteed not to lie on a wall).

Output

Print a single line listing the minimum number of doors which need to be created, in the format shown below.

Sample Input

7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4

Sample Output

Number of doors = 2

Source

East Central North America 1999

题目类型：线段相交+构造

算法分析：由于内部的线段是从外墙的一个边到另一个边的，所以若从外墙的某一个点开始找宝物一定会遇到k个墙的话，则最少会炸k个墙。所以可以枚举外墙上的每个点与宝物位置构造线段，然后判断与剩下的线段相交的交点数，取最少的即可。一个简单优化是内墙与外墙的交点是最少满足条件的点，所以可以直接枚举内墙的端点和外墙的4个端点而不用枚举外墙上的所有点

/*************************************************
Author        :supermaker
Created Time  :2016/1/30 13:32:18
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 = 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;
	}
};

struct Line
{
	Point s, e;
	Line () {}
	Line (Point ss, Point ee) : s (ss), e (ee) {}
};

bool Inter (Line l1, Line l2)
{
	return 
	max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&
	max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&
	max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&
	max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&
	sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e) ) <= 0 &&
	sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e))<= 0;
			
}

int n;
Point p[maxn*2], pp[6] = {Point (0, 0), Point (0, 100), Point (100, 0), Point (100, 100)};
Line l[maxn];

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		for (int i = 1; i <= n; i++)
		{
			double x1, y1, x2, y2;
			scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			l[i] = Line (Point (x1, y1), Point (x2, y2));
			p[i*2-1] = Point (x1, y1);
			p[i*2] = Point (x2, y2);
		}
		
		double x0, y0;
		scanf ("%lf%lf", &x0, &y0);
		Point e = Point (x0, y0);
		int res = INF;
		for (int i = 1; i <= 2 * n; i++)
		{
			Line tt = Line (e, p[i]);
			int cnt = 0;
			for (int j = 1; j <= n; j++)
				if (Inter (tt, l[j]))
						cnt++;
			res = min (res, cnt);
		}

		for (int i = 1; i <= 4; i++)
		{
			Line tt = Line (e, pp[i]);
			int cnt = 0;
			for (int j = 1; j <= n; j++)
				if (Inter (tt, l[j]))
					cnt++;
			res = min (res, cnt + 1);
		}

		printf ("Number of doors = %d\n", res);
	}	
    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

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

Author :supermaker

Created Time :2016/1/30 13:32:18

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 = 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;

}

};

struct Line

{

Point s, e;

Line () {}

Line (Point ss, Point ee) : s (ss), e (ee) {}

};

bool Inter (Line l1, Line l2)

{

return

max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&

max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&

max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&

max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&

sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e) ) <= 0 &&

sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e))<= 0;

}

int n;

Point p[maxn*2], pp[6] = {Point (0, 0), Point (0, 100), Point (100, 0), Point (100, 100)};

Line l[maxn];

int main()

{

//CFF;

//CPPFF;

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

{

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

{

double x1, y1, x2, y2;

scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

l[i] = Line (Point (x1, y1), Point (x2, y2));

p[i*2-1] = Point (x1, y1);

p[i*2] = Point (x2, y2);

}

double x0, y0;

scanf ("%lf%lf", &x0, &y0);

Point e = Point (x0, y0);

int res = INF;

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

{

Line tt = Line (e, p[i]);

int cnt = 0;

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

if (Inter (tt, l[j]))

cnt++;

res = min (res, cnt);

}

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

{

Line tt = Line (e, pp[i]);

int cnt = 0;

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

if (Inter (tt, l[j]))

cnt++;

res = min (res, cnt + 1);

}

printf ("Number of doors = %d\n", res);

}

return 0;

}

poj1329

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

30 1月 2016

Circle Through Three Points

Your team is to write a program that, given the Cartesian coordinates of three points on a plane, will find the equation of the circle through them all. The three points will not be on a straight line. 阅读全文 »

poj2653

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

29 1月 2016

Pick-up sticks

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

The picture to the right below illustrates the first case from input.

Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Sample Output

Top sticks: 2, 4, 5.

Top sticks: 1, 2, 3.

Hint

Huge input,scanf is recommended.

Source

Waterloo local 2005.09.17

题目类型：线段相交

算法分析：直接双重枚举判断每个线段是否与被后边的线段相交即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 20:44:22
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 + 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;
	}
};

struct Line
{
	Point s, e;
	Line () {}
	Line (Point ss, Point ee) : s (ss), e (ee) {}
};

int n;
Line l[maxn];
vector <int> res;

bool Inter (Line l1, Line l2)
{
	return 
	max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&
	max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&
	max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&
	max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&
	sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&
	sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == 0) break;
		for (int i = 1; i <= n; i++)
			scanf ("%lf%lf%lf%lf", &l[i].s.x, &l[i].s.y, &l[i].e.x, &l[i].e.y);
		
		res.clear ();
		for (int i = 1; i <= n; i++)
		{
			bool is_over = false;
			for (int j = i + 1; j <= n; j++)
				if (Inter (l[i], l[j]))
				{
					is_over = true;
					break;
				}
			if (!is_over)
				res.push_back (i);
		}
		
		printf ("Top sticks:");
		for (int i = 0; i < res.size (); i++)
		{
			if (i == res.size () - 1)
				printf (" %d.\n", res[i]);
			else
				printf (" %d,", res[i]);
		}
	}
    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

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

Author :supermaker

Created Time :2016/1/29 20:44:22

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 + 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;

}

};

struct Line

{

Point s, e;

Line () {}

Line (Point ss, Point ee) : s (ss), e (ee) {}

};

int n;

Line l[maxn];

vector <int> res;

bool Inter (Line l1, Line l2)

{

return

max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&

max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&

max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&

max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&

sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&

sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;

}

int main()

{

//CFF;

//CPPFF;

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

{

if (n == 0) break;

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

scanf ("%lf%lf%lf%lf", &l[i].s.x, &l[i].s.y, &l[i].e.x, &l[i].e.y);

res.clear ();

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

{

bool is_over = false;

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

if (Inter (l[i], l[j]))

{

is_over = true;

break;

}

if (!is_over)

res.push_back (i);

}

printf ("Top sticks:");

for (int i = 0; i < res.size (); i++)

{

if (i == res.size () - 1)

printf (" %d.\n", res[i]);

else

printf (" %d,", res[i]);

}

return 0;

}

poj1556

maksyuki 发表于 oj 分类，标签: 图论-最短路, 计算几何-点线面\点积\叉积

29 1月 2016

The Doors

You are to find the length of the shortest path through a chamber containing obstructing walls. The chamber will always have sides at x = 0, x = 10, y = 0, and y = 10. The initial and final points of the path are always (0, 5) and (10, 5). There will also be from 0 to 18 vertical walls inside the chamber, each with two doorways. The figure below illustrates such a chamber and also shows the path of minimal length.

Input

The input data for the illustrated chamber would appear as follows.

2
4 2 7 8 9
7 3 4.5 6 7

The first line contains the number of interior walls. Then there is a line for each such wall, containing five real numbers. The first number is the x coordinate of the wall (0 < x < 10), and the remaining four are the y coordinates of the ends of the doorways in that wall. The x coordinates of the walls are in increasing order, and within each line the y coordinates are in increasing order. The input file will contain at least one such set of data. The end of the data comes when the number of walls is -1.

Output

The output should contain one line of output for each chamber. The line should contain the minimal path length rounded to two decimal places past the decimal point, and always showing the two decimal places past the decimal point. The line should contain no blanks.

Sample Input

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1

Sample Output

10.00

10.06

Source

Mid-Central USA 1996

题目类型：线段相交+最短路

算法分析：由题易知只有每次走门的端点而不是走中间才能保证两点之间的边是最短的。枚举任意两点构造线段判断是否与图中的竖墙的分隔线段相交，分类讨论之后在满足条件的点之间连边，最后跑一个最短路即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 18:24:35
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 = 100 + 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;
	}
};

struct Line
{
	Point s, e;
	Line () {}
	Line (Point ss, Point ee) : s (ss), e (ee) {}
};

Point p[maxn];
Line l[maxn];
int n;
double edge[maxn][maxn], dis[maxn];;

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

bool inter (Line l1, Line l2)
{
	return 
	max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&
	max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&
	max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&
	max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&
	sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&
	sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
}

void Dij (int s)
{
	fill (dis, dis + maxn, INF);
	dis[s] = 0;
	priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu;
	qu.push (pair <int, double> (s, 0));
	while (!qu.empty ())
	{
		pair <int, double> tt = qu.top (); qu.pop ();
		int ta = tt.first;
		double tb = tt.second;
		if (sgn (dis[ta] - tb) < 0) continue;
		for (int i = 1; i <= 4 * n + 2; i++)
			if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta])
			{
				dis[i] = edge[ta][i] + dis[ta];
				qu.push (pair <int, double> (i, dis[i]));
			}
	}
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == -1) break;
		
		p[1] = Point (0, 5);
		p[4*n+2] = Point (10, 5);
		int tota = 1, totb = 0;
		for (int i = 1; i <= n; i++)
		{
			double x, y;
			scanf ("%lf", &x);
			for (int j = 1; j <= 4; j++)
			{
				scanf ("%lf", &y);	
				p[++tota] = Point (x, y);	
				if (j == 1)
					l[++totb] = Line (Point (x, 0), Point (x, y));
				else if (j == 3)
					l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y));
				else if (j == 4)
					l[++totb] = Line (Point (x, y), Point (x, 10));
			}	
		}
		
		for (int i = 0; i < maxn; i++)
			for (int j = 0; j < maxn; j++)
				edge[i][j] = INF;

		for (int i = 1; i <= 4 * n + 2; i++)
			for (int j = i + 1; j <= 4 * n + 2; j++)
			{
				int cnt = 0;
				for (int k = 1; k <= 3 * n; k++)
				{
					Line tt = Line (p[i], p[j]);
					if (inter (tt, l[k]))
						cnt++;
				}
				if (i == 1 && j < 4 * n + 2 && cnt == 1) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i == 1 && j == 4 * n + 2 && cnt == 0) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i != 1 && j < 4 * n + 2 && cnt == 2) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
				if (i != 1 && j == 4 * n + 2 && cnt == 1) 
					edge[i][j] = edge[j][i] = Dist (p[i], p[j]);	
			}
		
		for (int i = 1; i <= n; i++)
		{
			int ta = 4 * i - 2, tb =  ta + 1;
			edge[ta][ta+2] = edge[ta+2][ta] = INF;
			edge[tb][tb+2] = edge[tb+2][tb] = INF;
		}
		Dij (1);
		//for (int i = 1; i <= 4 * n + 2; i++)
	//	{
	//		for (int j = 1; j <= 4 * n + 2; j++)
	//			if (edge[i][j] < INF)
	//				cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl;
	//	}
		printf ("%.2f\n", dis[4*n+2]);
	}
    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

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

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

Author :supermaker

Created Time :2016/1/29 18:24:35

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 = 100 + 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;

}

};

struct Line

{

Point s, e;

Line () {}

Line (Point ss, Point ee) : s (ss), e (ee) {}

};

Point p[maxn];

Line l[maxn];

int n;

double edge[maxn][maxn], dis[maxn];;

double Dist (Point p1, Point p2)

{

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

}

bool inter (Line l1, Line l2)

{

return

max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) &&

max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) &&

max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) &&

max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) &&

sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&

sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;

}

void Dij (int s)

{

fill (dis, dis + maxn, INF);

dis[s] = 0;

priority_queue <pair <int, double>, vector <pair <int, double> >, greater <pair <int, double> > > qu;

qu.push (pair <int, double> (s, 0));

while (!qu.empty ())

{

pair <int, double> tt = qu.top (); qu.pop ();

int ta = tt.first;

double tb = tt.second;

if (sgn (dis[ta] - tb) < 0) continue;

for (int i = 1; i <= 4 * n + 2; i++)

if (i != s && edge[ta][i] < INF && dis[i] > edge[ta][i] + dis[ta])

{

dis[i] = edge[ta][i] + dis[ta];

qu.push (pair <int, double> (i, dis[i]));

}

int main()

{

//CFF;

//CPPFF;

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

{

if (n == -1) break;

p[1] = Point (0, 5);

p[4*n+2] = Point (10, 5);

int tota = 1, totb = 0;

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

{

double x, y;

scanf ("%lf", &x);

for (int j = 1; j <= 4; j++)

{

scanf ("%lf", &y);

p[++tota] = Point (x, y);

if (j == 1)

l[++totb] = Line (Point (x, 0), Point (x, y));

else if (j == 3)

l[++totb] = Line (Point (p[tota-1].x, p[tota-1].y), Point (x, y));

else if (j == 4)

l[++totb] = Line (Point (x, y), Point (x, 10));

}

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

for (int j = 0; j < maxn; j++)

edge[i][j] = INF;

for (int i = 1; i <= 4 * n + 2; i++)

for (int j = i + 1; j <= 4 * n + 2; j++)

{

int cnt = 0;

for (int k = 1; k <= 3 * n; k++)

{

Line tt = Line (p[i], p[j]);

if (inter (tt, l[k]))

cnt++;

}

if (i == 1 && j < 4 * n + 2 && cnt == 1)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i == 1 && j == 4 * n + 2 && cnt == 0)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i != 1 && j < 4 * n + 2 && cnt == 2)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

if (i != 1 && j == 4 * n + 2 && cnt == 1)

edge[i][j] = edge[j][i] = Dist (p[i], p[j]);

}

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

{

int ta = 4 * i - 2, tb = ta + 1;

edge[ta][ta+2] = edge[ta+2][ta] = INF;

edge[tb][tb+2] = edge[tb+2][tb] = INF;

}

Dij (1);

//for (int i = 1; i <= 4 * n + 2; i++)

// {

// for (int j = 1; j <= 4 * n + 2; j++)

// if (edge[i][j] < INF)

// cout << "i:" << i << " j:" << j << " edge[i][j]:" << edge[i][j] << endl;

// }

printf ("%.2f\n", dis[4*n+2]);

}

return 0;

}

poj3111

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

29 1月 2016

K Best

Demy has n jewels. Each of her jewels has some value v_i and weight w_i.

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …, i_k} as

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

Input

The first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).

The following n lines contain two integer numbers each — v_i and w_i (0 ≤ v_i ≤ 10⁶, 1 ≤ w_i ≤ 10⁶, both the sum of all v_i and the sum of all w_i do not exceed 10⁷).

Output

Output k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

Sample Input

3 2
1 1
1 2
1 3

Sample Output

1 2

Source

Northeastern Europe 2005, Northern Subregion

题目类型：最大化平均值(二分)

算法分析：原问题可以转化为求解”单位价值大于等于x”的最大的x。则每次判断是否满足拿k个物品使得vi-x*wi大于等于0，对于满足条件的方案要记录下来。当然这里要贪心地拿最高的k个。注意这里卡STL！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 13:17:22
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
{
	int v, w, id;	
	double y;
	bool operator < (const point &a) const
	{
		return y > a.y;
	}
};

int n, k;
point aa[maxn];

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

bool TT (double x)
{
	for (int i = 1; i <= n; i++)
		aa[i].y = aa[i].v - x * aa[i].w;
	sort (aa + 1, aa + 1 + n);

	double ans = 0;
	for (int i = 1; i <= n && i <= k; i++)
		ans += aa[i].y;

	if (sgn (ans) >= 0) return true;
	else return false;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf ("%d%d", &aa[i].v, &aa[i].w);
			aa[i].id = i;
		}

		double low = 0, high = 3e6, mid;
		int tot = 1;
		while (tot <= 100)
		{
			mid = (low + high) / 2.0;
			if (TT (mid)) low = mid;
			else high = mid;
			tot++;
		}
		
		for (int i = 1; i <= k; i++)
		{
			if (i == 1) printf ("%d", aa[i].id);
			else printf (" %d", aa[i].id);
		}
		puts ("");
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

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

Author :supermaker

Created Time :2016/1/29 13:17:22

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

{

int v, w, id;

double y;

bool operator < (const point &a) const

{

return y > a.y;

}

};

int n, k;

point aa[maxn];

inline int sgn (double val)

{

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

else if (val < 0) return -1;

return 1;

}

bool TT (double x)

{

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

aa[i].y = aa[i].v - x * aa[i].w;

sort (aa + 1, aa + 1 + n);

double ans = 0;

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

ans += aa[i].y;

if (sgn (ans) >= 0) return true;

else return false;

}

int main()

{

//CFF;

//CPPFF;

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

{

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

{

scanf ("%d%d", &aa[i].v, &aa[i].w);

aa[i].id = i;

}

double low = 0, high = 3e6, mid;

int tot = 1;

while (tot <= 100)

{

mid = (low + high) / 2.0;

if (TT (mid)) low = mid;

else high = mid;

tot++;

}

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

{

if (i == 1) printf ("%d", aa[i].id);

else printf (" %d", aa[i].id);

}

puts ("");

}

return 0;

}

poj2976

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

29 1月 2016

Dropping tests

In a certain course, you take n tests. If you get a_i out of b_i questions correct on test i, your cumulative average is defined to be. Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating a_i for all i. The third line contains n positive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

Sample Output

100

Hint

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

Source

Stanford Local 2005

题目类型：最大化平均值(二分)

算法分析：原问题可以转化为求解”单位价值大于等于x”的最大的x。则每次判断是否满足拿n-k的物品使得vi-x*wi大于等于0，当然这里要贪心地拿最高的k个

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 12:47:33
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 = 1e3 + 66;

int v[maxn], w[maxn], n, k;
double aa[maxn];

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

bool TT (double x)
{
	for (int i = 1; i <= n; i++)
		aa[i] = v[i] - x * w[i];
	sort (aa + 1, aa + 1 + n, greater <double> ()); 

	double res = 0;
	for (int i = 1; i <= n && i <= n - k; i++)
		res += aa[i];
	
	if (sgn (res) >= 0) return true;
	return false;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		if (n == 0 && k == 0) break;
		for (int i = 1; i <= n; i++)
			scanf ("%d", &v[i]);

		for (int i = 1; i <= n; i++)
			scanf ("%d", &w[i]);
	
		double low = 0, high = 6e16, mid;
		int tot = 1;
		while (tot <= 100)
		{
			mid = (low + high) / 2.0; 
			if (TT (mid)) low = mid;
			else high = mid;
			tot++;
		}

		printf ("%.lf\n", mid * 100);
	}
    return 0;
}

100

101

102

103

104

105

106

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

Author :supermaker

Created Time :2016/1/29 12:47:33

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 = 1e3 + 66;

int v[maxn], w[maxn], n, k;

double aa[maxn];

int sgn (double val)

{

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

else if (val < 0) return -1;

return 1;

}

bool TT (double x)

{

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

aa[i] = v[i] - x * w[i];

sort (aa + 1, aa + 1 + n, greater <double> ());

double res = 0;

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

res += aa[i];

if (sgn (res) >= 0) return true;

return false;

}

int main()

{

//CFF;

//CPPFF;

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

{

if (n == 0 && k == 0) break;

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

scanf ("%d", &v[i]);

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

scanf ("%d", &w[i]);

double low = 0, high = 6e16, mid;

int tot = 1;

while (tot <= 100)

{

mid = (low + high) / 2.0;

if (TT (mid)) low = mid;

else high = mid;

tot++;

}

printf ("%.lf\n", mid * 100);

}

return 0;

}

poj2954

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

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;

}

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

maksyuki 发表于比赛分类，标签: 比赛-codeforces

27 1月 2016

A Elephant

An elephant decided to visit his friend. It turned out that the elephant's house is located at point 0 and his friend's house is located at point x(x > 0) of the coordinate line. In one step the elephant 阅读全文 »

poj2187

maksyuki 发表于 oj 分类，标签: 计算几何-旋转卡壳

27 1月 2016

Beauty Contest

Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around 阅读全文 »

poj1873

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

27 1月 2016

The Fortified Forest

Once upon a time, in a faraway land, there lived a king. This king owned a small collection of rare and valuable trees, which had been gathered by his ancestors on their travels. To protect his trees from thieves, the king ordered that a high fence be built around them. His wizard was put in charge of the operation.
Alas, the wizard quickly noticed that the only suitable material available to build the fence was the wood from the trees themselves. In other words, it was necessary to cut down some trees in order to build a fence around the remaining trees. Of course, to prevent his head from being chopped off, the wizard wanted to minimize the value of the trees that had to be cut. The wizard went to his tower and stayed there until he had found the best possible solution to the problem. The fence was then built and everyone lived happily ever after.

You are to write a program that solves the problem the wizard faced.

Input

The input contains several test cases, each of which describes a hypothetical forest. Each test case begins with a line containing a single integer n, 2 <= n <= 15, the number of trees in the forest. The trees are identified by consecutive integers 1 to n. Each of the subsequent n lines contains 4 integers xi, yi, vi, li that describe a single tree. (xi, yi) is the position of the tree in the plane, vi is its value, and li is the length of fence that can be built using the wood of the tree. vi and li are between 0 and 10,000.
The input ends with an empty test case (n = 0).

Output

For each test case, compute a subset of the trees such that, using the wood from that subset, the remaining trees can be enclosed in a single fence. Find the subset with minimum value. If more than one such minimum-value subset exists, choose one with the smallest number of trees. For simplicity, regard the trees as having zero diameter.
Display, as shown below, the test case numbers (1, 2, ...), the identity of each tree to be cut, and the length of the excess fencing (accurate to two fractional digits).

Display a blank line between test cases.

Sample Input

6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8

3
3 0 10 2
5 5 20 25
7 -3 30 32

Sample Output

Forest 1

Cut these trees: 2 4 5

Extra wood: 3.16

Forest 2

Cut these trees: 2

Extra wood: 15.00

Source

World Finals 1999

题目类型：二进制枚举+凸包

算法分析：由于n比较小，所以可以使用二进制枚举子集的方法来删点，然后求剩下点的凸包，并按照val值和len的限制更新答案。注意若最后只剩下一个点，则此时凸包周长为0！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/27 13:44:04
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 = 66 + 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], tp[maxn];
int val[maxn], llen[maxn], n, tp_len;
int cur_val, cur_len;
int fin_val, fin_num, fin_res;
double fin_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 - tp[1]) ^ (p2 - tp[1]);
	if (sgn (tt) == 1) return true;
	else if (sgn (tt) == 0 && sgn (Dist (p1, tp[1]) - Dist (p2, tp[1])) <= 0) return true;
	return false;
}

double Garham ()
{
	Point start = tp[1];		
	int start_pos = 1;
	for (int i = 1; i <= tp_len; i++)
		if (sgn (tp[i].x - start.x) == -1 || (sgn (tp[i].x - start.x) == 0 && sgn (tp[i].y - start.y) == -1))
			start = tp[i], start_pos = i;

	swap (tp[start_pos], tp[1]);
	sort (tp + 2, tp + 1 + tp_len, polarcmp);
	while (!sta.empty ()) sta.pop ();

	if (tp_len == 0) return 0;
	else if (tp_len == 1) return 0;
	else if (tp_len == 2) return 2.0 * Dist (tp[1], tp[2]);
	else
	{
		sta.push (1), sta.push (2);
		for (int i = 3; i <= tp_len; i++)
		{
			while (sta.size () >= 2)
			{
				int tt1 = sta.top (); sta.pop ();
				int tt2 = sta.top (); sta.pop ();
				if (sgn ((tp[tt1] - tp[tt2]) ^ (tp[i] - tp[tt2])) <= 0) 
					sta.push (tt2);

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

		double res = 0;
		int per = sta.top (); sta.pop ();
		int cur = per, beg = per;
		while (!sta.empty ())
		{
			cur = sta.top (); sta.pop ();
			res += Dist (tp[per], tp[cur]);
			per = cur;
		}
		res += Dist (tp[cur], tp[beg]);
		return res;
	}
}

int main()
{
    //CFF;
    //CPPFF;
	int flag = 1;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == 0) break;
		for (int i = 1; i <= n; i++)
			scanf ("%lf%lf%d%d", &p[i].x, &p[i].y, &val[i], &llen[i]);
		
		fin_val = fin_num = INF; 
		fin_res = 0;
		fin_len = INF;
		for (int i = 0; i < (1 << n); i++)
		{
			cur_val = cur_len = tp_len = 0;
			for (int j = 1; j <= n; j++)
			{
				if (i & (1 << (j - 1)))
					cur_val += val[j], cur_len += llen[j];

				else
					tp[++tp_len] = p[j];
			}
	
			if (cur_val > fin_val) continue;
			double tt = Garham ();
			if (sgn (cur_len - tt) == 1)	
			{
				if (cur_val < fin_val || (cur_val == fin_val && n - tp_len < fin_num))
				{
					fin_val = cur_val;
					fin_num = n - tp_len;
					fin_res = i;
					fin_len = cur_len - tt;
				}
			}
		}

		if (flag > 1) puts ("");
		printf ("Forest %d\n", flag++);
		printf ("Cut these trees:");
		for (int i = 1; i <= n; i++)
			if (fin_res & (1 << (i - 1)))
				printf (" %d", i);
		puts ("");
		printf ("Extra wood: %.2f\n", fin_len);
	}
    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

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

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

Author :supermaker

Created Time :2016/1/27 13:44:04

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 = 66 + 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], tp[maxn];

int val[maxn], llen[maxn], n, tp_len;

int cur_val, cur_len;

int fin_val, fin_num, fin_res;

double fin_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 - tp[1]) ^ (p2 - tp[1]);

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

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

return false;

}

double Garham ()

{

Point start = tp[1];

int start_pos = 1;

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

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

start = tp[i], start_pos = i;

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

sort (tp + 2, tp + 1 + tp_len, polarcmp);

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

if (tp_len == 0) return 0;

else if (tp_len == 1) return 0;

else if (tp_len == 2) return 2.0 * Dist (tp[1], tp[2]);

else

{

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

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

{

while (sta.size () >= 2)

{

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

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

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

sta.push (tt2);

else

{

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

break;

}

sta.push (i);

}

double res = 0;

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

int cur = per, beg = per;

while (!sta.empty ())

{

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

res += Dist (tp[per], tp[cur]);

per = cur;

}

res += Dist (tp[cur], tp[beg]);

return res;

}

int main()

{

//CFF;

//CPPFF;

int flag = 1;

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

{

if (n == 0) break;

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

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

fin_val = fin_num = INF;

fin_res = 0;

fin_len = INF;

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

{

cur_val = cur_len = tp_len = 0;

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

{

if (i & (1 << (j - 1)))

cur_val += val[j], cur_len += llen[j];

else

tp[++tp_len] = p[j];

}

if (cur_val > fin_val) continue;

double tt = Garham ();

if (sgn (cur_len - tt) == 1)

{

if (cur_val < fin_val || (cur_val == fin_val && n - tp_len < fin_num))

{

fin_val = cur_val;

fin_num = n - tp_len;

fin_res = i;

fin_len = cur_len - tt;

}

if (flag > 1) puts ("");

printf ("Forest %d\n", flag++);

printf ("Cut these trees:");

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

if (fin_res & (1 << (i - 1)))

printf (" %d", i);

puts ("");

printf ("Extra wood: %.2f\n", fin_len);

}

return 0;

}

poj2007

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

26 1月 2016

Scrambled Polygon

A closed polygon is a figure bounded by a finite number of line segments. The intersections of the bounding line segments are called the vertices of the polygon. When one starts at any vertex of a closed polygon and traverses each bounding line segment exactly once, one comes back to the starting vertex.

A closed polygon is called convex if the line segment joining any two points of the polygon lies in the polygon. Figure 1 shows a closed polygon which is convex and one which is not convex. (Informally, a closed polygon is convex if its border doesn't have any "dents".)
The subject of this problem is a closed convex polygon in the coordinate plane, one of whose vertices is the origin (x = 0, y = 0). Figure 2 shows an example. Such a polygon will have two properties significant for this problem.

The first property is that the vertices of the polygon will be confined to three or fewer of the four quadrants of the coordinate plane. In the example shown in Figure 2, none of the vertices are in the second quadrant (where x < 0, y > 0).

To describe the second property, suppose you "take a trip" around the polygon: start at (0, 0), visit all other vertices exactly once, and arrive at (0, 0). As you visit each vertex (other than (0, 0)), draw the diagonal that connects the current vertex with (0, 0), and calculate the slope of this diagonal. Then, within each quadrant, the slopes of these diagonals will form a decreasing or increasing sequence of numbers, i.e., they will be sorted. Figure 3 illustrates this point.

Input

The input lists the vertices of a closed convex polygon in the plane. The number of lines in the input will be at least three but no more than 50. Each line contains the x and y coordinates of one vertex. Each x and y coordinate is an integer in the range -999..999. The vertex on the first line of the input file will be the origin, i.e., x = 0 and y = 0. Otherwise, the vertices may be in a scrambled order. Except for the origin, no vertex will be on the x-axis or the y-axis. No three vertices are colinear.

Output

The output lists the vertices of the given polygon, one vertex per line. Each vertex from the input appears exactly once in the output. The origin (0,0) is the vertex on the first line of the output. The order of vertices in the output will determine a trip taken along the polygon's border, in the counterclockwise direction. The output format for each vertex is (x,y) as shown below.

Sample Input

0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10

Sample Output

(0,0)

(-30,-40)

(-30,-50)

(-10,-60)

(50,-60)

(70,-50)

(90,-20)

(90,10)

(80,20)

(60,30)

Source

Rocky Mountain 2004

题目类型：求凸包+输出方案

算法分析：使用Garham算法求解即可，注意栈中的方案是顺时针序的，需要进行一个简单转换

/*************************************************
Author        :supermaker
Created Time  :2016/1/26 21:11:32
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 = 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);
	}

	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];
int n;
stack <int> sta;
vector <Point> res;

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 ();

	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);
	}
}

int main()
{
    //CFF;
    //CPPFF;
	n = 0;
	double sx, sy;
	while (scanf ("%lf%lf", &sx, &sy) != EOF)
	{
		p[++n] = Point (sx, sy);
	}

	Garham ();
	res.clear ();
	while (!sta.empty ())
	{
		int tt = sta.top (); sta.pop ();
		res.push_back (p[tt]);	
	}
		
	vector <Point> ans;	
	set <int> seta;
	bool is_have = false;
	for (int i = res.size () - 1; i >= 0; i--)
	{
		if (sgn (res[i].x) == 0 && sgn (res[i].y) == 0)
			ans.push_back (res[i]), is_have = true, seta.insert (i);
			
		else if (is_have)
			ans.push_back (res[i]), seta.insert (i);
	}

	for (int i = res.size () - 1; i >= 0; i--)
		if (seta.find (i) == seta.end ())
			ans.push_back (res[i]), seta.insert (i);

	for (int i = 0; i < ans.size (); i++)
		printf ("(%.lf,%.lf)\n", ans[i].x, ans[i].y);
    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

167

168

169

170

171

172

173

174

175

176

177

178

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

Author :supermaker

Created Time :2016/1/26 21:11:32

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 = 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);

}

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];

int n;

stack <int> sta;

vector <Point> res;

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 ();

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);

}

int main()

{

//CFF;

//CPPFF;

n = 0;

double sx, sy;

while (scanf ("%lf%lf", &sx, &sy) != EOF)

{

p[++n] = Point (sx, sy);

}

Garham ();

res.clear ();

while (!sta.empty ())

{

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

res.push_back (p[tt]);

}

vector <Point> ans;

set <int> seta;

bool is_have = false;

for (int i = res.size () - 1; i >= 0; i--)

{

if (sgn (res[i].x) == 0 && sgn (res[i].y) == 0)

ans.push_back (res[i]), is_have = true, seta.insert (i);

else if (is_have)

ans.push_back (res[i]), seta.insert (i);

}

for (int i = res.size () - 1; i >= 0; i--)

if (seta.find (i) == seta.end ())

ans.push_back (res[i]), seta.insert (i);

for (int i = 0; i < ans.size (); i++)

printf ("(%.lf,%.lf)\n", ans[i].x, ans[i].y);

return 0;

}

1 2 3 下一页最后一页

超客的水墨烟雨

poj2139

poj2449

poj1066

poj1329

poj2653

poj1556

poj3111

poj2976

poj2954

poj1265

poj1654

poj3348

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

poj2187

poj1873

poj2007

分类目录

标签云

书签

近期评论

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