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

poj3160

maksyuki 发表于 oj 分类，标签: DP-线性DP, 图论-有向图强连通分量

24 1月 2016

Father Christmas flymouse

After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.

During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.

Input

The input contains several test cases. Each test cases start with two integers N and M not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were N team members living in N distinct rooms and M direct paths. On the next N lines there are N integers, one on each line, the i-th of which gives the comfort index of the words of the team member in the i-th room. Then follow M lines, each containing two integers i and j indicating a directed path from the i-th room to the j-th one. Process to end of file.

Output

For each test case, output one line with only the maximized sum of accumulated comfort indices.

Sample Input

2 2
14
21
0 1
1 0

Sample Output

Hint

32-bit signed integer type is capable of doing all arithmetic.

Source

POJ Monthly--2006.12.31, Sempr

题目类型：有向图强连通分量+缩点+DP

算法分析：易知在同一个强连通分量中的点的权值等于所有正值点的点权之和。缩点后，在构建出来的图上DP，dp[i]表示i点处的最大值，初始化为缩点后该点的点权。状态转移方程为dp[i] = max (dp[i], max (vval[i] + dp[j])), j至i有一条有向边，vval[i]为i点处的点权。最后使用拓扑序转移计算即可，注意若点权为负值，由于可以不进去，所以缩点后点权可以赋值为0！！！dp[i]要使用long long！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/24 18:56:38
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 = 30000 + 66;
	
int dfn[maxn], low[maxn], belong[maxn], val[maxn], vval[maxn], indeg[maxn];
LL dp[maxn];
int n, m, id, tot;
bool instack[maxn];
vector <int> g[maxn], gg[maxn];
stack <int> sta;

void dfs (int u)
{
	dfn[u] = low[u] = ++id;
	sta.push (u);
	instack[u] = true;
	for (int i = 0; i < g[u].size (); i++)
	{
		int v = g[u][i];
		if (!dfn[v])
		{
			dfs (v);
			low[u] = min (low[u], low[v]);
		}
		else if (instack[v])
			low[u] = min (low[u], dfn[v]);
	}

	if (low[u] == dfn[u])
	{
		tot++;
		int tt;
		do
		{
			tt = sta.top (); sta.pop ();
			instack[tt] = false;
			belong[tt] = tot;
			if (val[tt] > 0) 
				vval[tot] += val[tt];
		} while (!sta.empty () && tt != u);
	}
}

void SS ()
{
	memset (dfn, 0, sizeof (dfn));
	memset (low, 0, sizeof (low));
	memset (instack, false, sizeof (instack));
	memset (vval, 0, sizeof (vval));
	tot = id = 0;
	while (!sta.empty ()) sta.pop ();
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			dfs (i);
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf ("%d", &val[i]);

		for (int i = 0; i < maxn; i++)
			g[i].clear ();

		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			u++, v++;
			g[u].push_back (v);
		}

		SS ();
		memset (indeg, 0, sizeof (indeg));
		for (int i = 0; i < maxn; i++)
			gg[i].clear ();
		for (int u = 1; u <= n; u++)
			for (int i = 0; i < g[u].size (); i++)
			{
				int v = g[u][i];
				if (belong[u] != belong[v])
				{
					indeg[belong[v]]++;
					gg[belong[u]].push_back (belong[v]);
				}
			}
	
		queue <int> qu;
		for (int i = 1; i <= tot; i++)
		{
			if (!indeg[i])
				qu.push (i);
			dp[i] = vval[i];	
		}
			
		while (!qu.empty ())
		{
			int tt = qu.front (); qu.pop ();
			for (int i = 0; i < gg[tt].size (); i++)
			{
				int v = gg[tt][i];
				indeg[v]--;
				dp[v] = max (dp[v], vval[v] + dp[tt]);
				if (!indeg[v])
					qu.push (v);
			}
		}
		
		LL res = -INF;
		for (int i = 1; i <= tot; i++)
			res = max (res, dp[i]);

		printf ("%lld\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

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

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

Author :supermaker

Created Time :2016/1/24 18:56:38

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

int dfn[maxn], low[maxn], belong[maxn], val[maxn], vval[maxn], indeg[maxn];

LL dp[maxn];

int n, m, id, tot;

bool instack[maxn];

vector <int> g[maxn], gg[maxn];

stack <int> sta;

void dfs (int u)

{

dfn[u] = low[u] = ++id;

sta.push (u);

instack[u] = true;

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (!dfn[v])

{

dfs (v);

low[u] = min (low[u], low[v]);

}

else if (instack[v])

low[u] = min (low[u], dfn[v]);

}

if (low[u] == dfn[u])

{

tot++;

int tt;

{

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

instack[tt] = false;

belong[tt] = tot;

if (val[tt] > 0)

vval[tot] += val[tt];

} while (!sta.empty () && tt != u);

}

void SS ()

{

memset (dfn, 0, sizeof (dfn));

memset (low, 0, sizeof (low));

memset (instack, false, sizeof (instack));

memset (vval, 0, sizeof (vval));

tot = id = 0;

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

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

if (!dfn[i])

dfs (i);

}

int main()

{

//CFF;

//CPPFF;

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

{

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

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

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

g[i].clear ();

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

{

int u, v;

scanf ("%d%d", &u, &v);

u++, v++;

g[u].push_back (v);

}

SS ();

memset (indeg, 0, sizeof (indeg));

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

gg[i].clear ();

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

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (belong[u] != belong[v])

{

indeg[belong[v]]++;

gg[belong[u]].push_back (belong[v]);

}

queue <int> qu;

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

{

if (!indeg[i])

qu.push (i);

dp[i] = vval[i];

}

while (!qu.empty ())

{

int tt = qu.front (); qu.pop ();

for (int i = 0; i < gg[tt].size (); i++)

{

int v = gg[tt][i];

indeg[v]--;

dp[v] = max (dp[v], vval[v] + dp[tt]);

if (!indeg[v])

qu.push (v);

}

LL res = -INF;

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

res = max (res, dp[i]);

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

}

return 0;

}

poj1269

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

24 1月 2016

Intersecting Lines

We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.

Input

The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).

Output

There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read "END OF OUTPUT".

Sample Input

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

Sample Output

INTERSECTING LINES OUTPUT

POINT 2.00 2.00

NONE

LINE

POINT 2.00 5.00

POINT 1.07 2.20

END OF OUTPUT

Source

Mid-Atlantic 1996

题目类型：直线相交

算法分析：对于每对直线，依次使用叉积判断是否是重合还是相交，然后再判断其中一条线矢量端点是否在另一条直线矢量端点为对角线的矩形内。若判断为相交，则使用矢量计算出交点

/*************************************************
Author        :supermaker
Created Time  :2016/1/24 14:50: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 = 1e5 + 6666;

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

	pair <int, Point> operator & (const Line &a) const
	{
		Point res = s;
		if (sgn ((s - e) ^ (a.s - a.e)) == 0)
		{
			if (sgn ((s - a.e) ^ (a.s - a.e)) == 0)
				return make_pair (0, res);
			else return make_pair (1, res);
		}
		double t = ((s - a.s) ^ (a.s - a.e)) / ((s - e) ^ (a.s - a.e));
		res.x += (e.x - s.x) * t;
		res.y += (e.y - s.y) * t;
		return make_pair (2, res);
	}
};

int main()
{
    //CFF;
    //CPPFF;
	int n;
	while (scanf ("%d", &n) != EOF)
	{
		double x1, y1, x2, y2, x3, y3, x4, y4;
		puts ("INTERSECTING LINES OUTPUT");
		for (int i = 1; i <= n; i++)
		{
			scanf ("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
			Line l1 (Point (x1, y1), Point (x2, y2));
			Line l2 (Point (x3, y3), Point (x4, y4));
			pair <int, Point> tt = l1 & l2;
			if (tt.first == 0) puts ("LINE");
			else if (tt.first == 1) puts ("NONE");
			else printf ("POINT %.2lf %.2lf\n", tt.second.x, tt.second.y);
		}
		puts ("END OF OUTPUT");
	}
    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

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

Author :supermaker

Created Time :2016/1/24 14:50: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 = 1e5 + 6666;

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

pair <int, Point> operator & (const Line &a) const

{

Point res = s;

if (sgn ((s - e) ^ (a.s - a.e)) == 0)

{

if (sgn ((s - a.e) ^ (a.s - a.e)) == 0)

return make_pair (0, res);

else return make_pair (1, res);

}

double t = ((s - a.s) ^ (a.s - a.e)) / ((s - e) ^ (a.s - a.e));

res.x += (e.x - s.x) * t;

res.y += (e.y - s.y) * t;

return make_pair (2, res);

}

};

int main()

{

//CFF;

//CPPFF;

int n;

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

{

double x1, y1, x2, y2, x3, y3, x4, y4;

puts ("INTERSECTING LINES OUTPUT");

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

{

scanf ("%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);

Line l1 (Point (x1, y1), Point (x2, y2));

Line l2 (Point (x3, y3), Point (x4, y4));

pair <int, Point> tt = l1 & l2;

if (tt.first == 0) puts ("LINE");

else if (tt.first == 1) puts ("NONE");

else printf ("POINT %.2lf %.2lf\n", tt.second.x, tt.second.y);

}

puts ("END OF OUTPUT");

}

return 0;

}

poj2398

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

24 1月 2016

Toy Storage

Mom and dad have a problem: their child, Reza, never puts his toys away when he is finished playing with them. They gave Reza a rectangular box to put his toys in. Unfortunately, Reza is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for Reza to find his favorite toys anymore.
Reza's parents came up with the following idea. They put cardboard partitions into the box. Even if Reza keeps throwing his toys into the box, at least toys that get thrown into different partitions stay separate. The box looks like this from the top:
We want for each positive integer t, such that there exists a partition with t toys, determine how many partitions have t, toys.

Input

The input consists of a number of cases. The first line consists of six integers n, m, x1, y1, x2, y2. The number of cardboards to form the partitions is n (0 < n <= 1000) and the number of toys is given in m (0 < m <= 1000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1, y1) and (x2, y2), respectively. The following n lines each consists of two integers Ui Li, indicating that the ends of the ith cardboard is at the coordinates (Ui, y1) and (Li, y2). You may assume that the cardboards do not intersect with each other. The next m lines each consists of two integers Xi Yi specifying where the ith toy has landed in the box. You may assume that no toy will land on a cardboard.

A line consisting of a single 0 terminates the input.

Output

For each box, first provide a header stating "Box" on a line of its own. After that, there will be one line of output per count (t > 0) of toys in a partition. The value t will be followed by a colon and a space, followed the number of partitions containing t toys. Output will be sorted in ascending order of t for each box.

Sample Input

4 10 0 10 100 0
20 20
80 80
60 60
40 40
5 10
15 10
95 10
25 10
65 10
75 10
35 10
45 10
55 10
85 10
5 6 0 10 60 0
4 3
15 30
3 1
6 8
10 10
2 1
2 8
1 5
5 5
40 10
7 9
0

Sample Output

Box

2: 5

Box

1: 4

2: 1

Source

Tehran 2003 Preliminary

题目类型：叉积+二分枚举

算法分析：使用叉积来判断点在一条直线的左右侧，可以二分枚举直线来判断。注意在枚举前要先将直线按照从左至右的顺序排好序！！！

/*************************************************
Author        :supermaker
Created Time  :2016/1/24 14:00:45
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 = 1000 + 66;

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


Line line[maxn];
int res[maxn], cnt[maxn], n, m;

double xmult (Point p1, Point p2, Point p3)
{
	return (p2 - p1) ^ (p3 - p1);
}

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

bool cmp (Line a, Line b)
{
	 return a.s.x < b.s.x; 
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == 0) break;
		scanf ("%d", &m);
		double x1, y1, x2, y2;
		scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

		for (int i = 1; i <= n; i++)
		{
			double Ui, Li;
			scanf ("%lf%lf", &Ui, &Li);
			line[i] = Line (Point (Ui, y1), Point (Li, y2));
		}
		
		sort (line + 1, line + 1 + n, cmp);

		memset (res, 0, sizeof (res));
		memset (cnt, 0, sizeof (cnt));
		for (int i = 1; i <= m; i++)
		{
			double x, y;
			scanf ("%lf%lf", &x, &y);
			int low = 1, high = n;
			while (low <= high)
			{
				int mid = (low + high) >> 1;
				double tt = xmult (line[mid].s, Point (x, y), line[mid].e);
				if (sgn (tt) == 1)
					high = mid - 1;
				else
					low = mid + 1;
			}
			res[max(low,high)]++;
		}
		puts ("Box");
		int maxval = -INF;
		for (int i = 1; i <= n + 1; i++)
		{
			cnt[res[i]]++;
			if (res[i])
				maxval = max (maxval, res[i]);
		}
		
		for (int i = 1; i <= maxval; i++)
			if (cnt[i])
				printf ("%d: %d\n", i, cnt[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

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

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

Author :supermaker

Created Time :2016/1/24 14:00:45

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

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

};

Line line[maxn];

int res[maxn], cnt[maxn], n, m;

double xmult (Point p1, Point p2, Point p3)

{

return (p2 - p1) ^ (p3 - p1);

}

int sgn (double val)

{

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

else if (val < 0) return -1;

return 1;

}

bool cmp (Line a, Line b)

{

return a.s.x < b.s.x;

}

int main()

{

//CFF;

//CPPFF;

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

{

if (n == 0) break;

scanf ("%d", &m);

double x1, y1, x2, y2;

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

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

{

double Ui, Li;

scanf ("%lf%lf", &Ui, &Li);

line[i] = Line (Point (Ui, y1), Point (Li, y2));

}

sort (line + 1, line + 1 + n, cmp);

memset (res, 0, sizeof (res));

memset (cnt, 0, sizeof (cnt));

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

{

double x, y;

scanf ("%lf%lf", &x, &y);

int low = 1, high = n;

while (low <= high)

{

int mid = (low + high) >> 1;

double tt = xmult (line[mid].s, Point (x, y), line[mid].e);

if (sgn (tt) == 1)

high = mid - 1;

else

low = mid + 1;

}

res[max(low,high)]++;

}

puts ("Box");

int maxval = -INF;

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

{

cnt[res[i]]++;

if (res[i])

maxval = max (maxval, res[i]);

}

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

if (cnt[i])

printf ("%d: %d\n", i, cnt[i]);

}

return 0;

}

poj2318

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

24 1月 2016

TOYS

Calculate the number of toys that land in each bin of a partitioned toy box.Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John's parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

Input

The input file contains one or more problems. The first line of a problem consists of six integers, n m x1 y1 x2 y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The following n lines contain two integers per line, Ui Li, indicating that the ends of the i-th cardboard partition is at the coordinates (Ui,y1) and (Li,y2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, Xj Yj specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.

Output

The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10

Sample Output

0: 2

1: 1

2: 1

3: 1

4: 0

5: 1

0: 2

1: 2

2: 2

3: 2

4: 2

Hint

As the example illustrates, toys that fall on the boundary of the box are "in" the box.

Source

Rocky Mountain 2003

题目类型：叉乘+二分枚举

算法分析：使用叉乘可以判断点在一个线段的左侧还是右侧。然后二分枚举直线并判断即可

/*************************************************
Author        :supermaker
Created Time  :2016/1/24 10:51:12
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 = 5000 * 2 + 66; 

int n, m;

int sgn (double a)
{
	if (fabs (a) < EPS) return 0;
	else if (a < 0) return -1;
	else 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;
	}
};

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


Line line[maxn];
int res[maxn];

double xmul (Point p1, Point p2, Point p3)
{
	return (p2 - p1) ^ (p3 - p1); 
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == 0) break;
		scanf ("%d", &m);
		double x1, y1, x2, y2;
		scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
	
		for (int i = 1; i <= n; i++)
		{
			double Ui, Li;
			scanf ("%lf%lf", &Ui, &Li);
			line[i] = Line (Point (Ui, y1), Point (Li, y2));	
		}

		memset (res, 0, sizeof (res));
		for (int i = 1; i <= m; i++)
		{
			double x, y;
			scanf ("%lf%lf", &x, &y);
			int low = 1, high = n;
			while (low <= high)
			{
				int mid = (low + high) >> 1;
				double tt = xmul (line[mid].s, Point (x, y), line[mid].e);
				if (sgn (tt) == 1)
					high = mid - 1;

				if (sgn (tt) == -1)
					low = mid + 1;
			}
			res[min(low,high)]++;
		}

		for (int i = 0; i <= n; i++)
			printf ("%d: %d\n", i, res[i]);
		puts ("");
	}
    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

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

Author :supermaker

Created Time :2016/1/24 10:51:12

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 = 5000 * 2 + 66;

int n, m;

int sgn (double a)

{

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

else if (a < 0) return -1;

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

}

};

struct Line

{

Point s, e;

Line () {}

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

};

Line line[maxn];

int res[maxn];

double xmul (Point p1, Point p2, Point p3)

{

return (p2 - p1) ^ (p3 - p1);

}

int main()

{

//CFF;

//CPPFF;

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

{

if (n == 0) break;

scanf ("%d", &m);

double x1, y1, x2, y2;

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

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

{

double Ui, Li;

scanf ("%lf%lf", &Ui, &Li);

line[i] = Line (Point (Ui, y1), Point (Li, y2));

}

memset (res, 0, sizeof (res));

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

{

double x, y;

scanf ("%lf%lf", &x, &y);

int low = 1, high = n;

while (low <= high)

{

int mid = (low + high) >> 1;

double tt = xmul (line[mid].s, Point (x, y), line[mid].e);

if (sgn (tt) == 1)

high = mid - 1;

if (sgn (tt) == -1)

low = mid + 1;

}

res[min(low,high)]++;

}

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

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

puts ("");

}

return 0;

}

超客的水墨烟雨

poj3160

poj1269

poj2398

poj2318

分类目录

标签云

书签

近期评论

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