Hstream

详见上一篇日志，POJ2954(http://sweetglue.blogbus.com/logs/36939861.html)

#include
#include
#include
using namespace std;

struct Point
{
	int x, y;
};

#define MAX 105
//加为了循环不越界
Point points[MAX+1];

int gcd(int i, int j)
{
	int a = max(i, j), b = min(i, j);
	i = a%b;
	while(i != 0)
	{
		a = b;
		b = i;
		i = a%b;
	}
	return b;
}

//计算在某条边上的整数点的数目（不包括端点），端点坐标必须为整数
int countPointsOnSegment(Point p1, Point p2)
{
	int a = abs(p2.y - p1.y), b = abs(p2.x - p1.x);
	if(a == 0 && b == 0)
		return 0;
	else if(a == 0)
		return b - 1;
	else if(b == 0)
		return a - 1;
	else
		return gcd(a, b) - 1;
}

//计算在多边形边上的整数点的数目（不包括端点），端点坐标必须为整数
int countPointsOnPolygon(int DIM)
{
	int res = 0;
	for(int i = 0; i < DIM; i++)
	{
		res += countPointsOnSegment(points[i], points[i+1]);
	}
	return res;
}

int areaPoly2(int DIM)
{
	int res = 0;
	for(int i = 0; i < DIM; i++)
	{
		res += (points[i].x + points[i+1].x)*(points[i+1].y - points[i].y);
	}
	return abs(res);
}

int countPointsInPolygon(int DIM)
{
	return (areaPoly2(DIM) - DIM - countPointsOnPolygon(DIM))/2 + 1;
}

int main()
{
	int t, cc, n;
	scanf("%d", &t);
	points[0].x = points[0].y = 0;
	for(cc = 1; cc <= t; cc++)
	{
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
		{
			scanf("%d%d", &points[i].x, &points[i].y);
			points[i].x += points[i-1].x;
			points[i].y += points[i-1].y;
		}
		points[n] = points[0];
		int in = countPointsInPolygon(n);
		int on = countPointsOnPolygon(n) + n;
		double area = (double)areaPoly2(n) / 2.0;
		printf("Scenario #%d:\n%d %d %.1lf\n\n", cc, in, on, area);
	}
	return 0;
}

Pick公式：a = e / 2 + i - 1 。其中a为多边形（顶点都在格点上）面积，e为多边形边上的格点数，i为多边形内部的格点数。

则多边形内部整数坐标点数为：(2a-e)/2+1

#include
#include
#include
using namespace std;

struct Point
{
	int x, y;
};

//多边形边数
#define DIM 3
//加1为了循环不越界
Point points[DIM+1];

int gcd(int i, int j)
{
	int a = max(i, j), b = min(i, j);
	i = a%b;
	while(i != 0)
	{
		a = b;
		b = i;
		i = a%b;
	}
	return b;
}

//计算在某条边上的整数点的数目（不包括端点），端点坐标必须为整数
int countPointsOnSegment(Point p1, Point p2)
{
	int a = abs(p2.y - p1.y), b = abs(p2.x - p1.x);
	if(a == 0 && b == 0)
		return 0;
	else if(a == 0)
		return b - 1;
	else if(b == 0)
		return a - 1;
	else
		return gcd(a, b) - 1;
}

//计算在多边形边上的整数点的数目（不包括端点），端点坐标必须为整数
int countPointsOnPolygon()
{
	int res = 0;
	for(int i = 0; i < DIM; i++)
	{
		res += countPointsOnSegment(points[i], points[i+1]);
	}
	return res;
}

int areaPoly2()
{
	int res = 0;
	for(int i = 0; i < DIM; i++)
	{
		res += (points[i].x + points[i+1].x)*(points[i+1].y - points[i].y);
	}
	return abs(res);
}

int countPointsInPolygon()
{
	return (areaPoly2() - DIM - countPointsOnPolygon())/2 + 1;
}

int main()
{
	while(true)
	{
		scanf("%d%d%d%d%d%d", &points[0].x, &points[0].y, &points[1].x, &points[1].y, &points[2].x, &points[2].y);
		if(points[0].x == 0 && points[0].y == 0 && points[1].x == 0 && points[1].y == 0 && points[2].x == 0 && points[2].y == 0)
			break;
		points[3] = points[0];
		printf("%d\n", countPointsInPolygon());
	}
	return 0;
}

每次选定一个点p，然后计算其他点与p构成的线段的斜率，记录斜率相同的最多的数目。

很奇怪的是，同样是n2logn的算法，用vector后sort不超时，但用map超时

#include
#include
#include
#include
using namespace std;

struct Point
{
	double x,y;
};

Point points[705];

double eps = 1e-6;

bool same(double x, double y)
{
	return abs(x-y) < eps;
}

int main()
{
	int n;
	double topp = 1e20;
	while(scanf("%d", &n), n != 0)
	{
		int maxs = 1;
		for(int i = 0; i < n; i++)
		{
			scanf("%lf%lf", &points[i].x, &points[i].y);
		}
		for(int i = 0; i < n; i++)
		{
			vector vect;
			for(int j = 0; j < n; j++)
			{
				if(j == i)
					continue;
				if(same(points[i].x, points[j].x))
					vect.push_back(topp);
				else
				{
					vect.push_back((points[j].y-points[i].y)/(points[j].x-points[i].x));
				}
			}
			sort(vect.begin(), vect.end());
			int counts = 1;
			for(int j = 1; j < vect.size(); j++)
			{
				if(same(vect[j], vect[j-1]))
				{
					counts++;
				}
				else
				{
					if(maxs < counts)
						maxs = counts;
					counts = 1;
				}
			}
			if(maxs < counts)
				maxs = counts;
		}
		printf("%d\n", maxs+1);
	}
	return 0;
}

这个题一个月前就在做，一直WA，百思不得其解，今天终于发现原来输出漏掉了逗号，郁闷。

判断一个线段是否在另一个上面的问题，需要完全相交（不包括一个的端点在另一个上面）

#include
#include
#include
using namespace std;

#define PI acos(-1)
#define eps 1e-6

typedef struct
{
	double x, y;
} Point;

typedef struct
{
	double x, y, r;
} Circle;

typedef struct
{
	double a, b, c;
} Line;


bool same(Point& p1, Point& p2)
{
	return abs(p1.x-p2.x) < eps && abs(p1.y-p2.y) < eps;
}
bool same(double x, double y)
{
	return abs(x-y) < eps;
}

double crossMul(Point p0, Point p1, Point p2)
{
	return (p2.x - p0.x) * (p1.y - p0.y) - (p1.x - p0.x) * (p2.y - p0.y);
}

//判断两线段是否相交(不包括一个端点在另一个上面）
bool isIntesect(Point s1, Point e1, Point s2, Point e2)
{
	return max(s1.x, e1.x) >= min(s2.x, e2.x) && max(s2.x, e2.x) >= min(s1.x, e1.x) && max(s1.y, e1.y) >= min(s2.y, e2.y) && max(s2.y, e2.y) >= min(s1.y, e1.y) && crossMul(s1, e1, s2)*crossMul(s1,e2, e1) > 0 && crossMul(s2, e2, s1)*crossMul(s2,e1, e2) > 0;
}

Point lines[100005][4];
bool ison[100005];

int main()
{
	int n;
	while(scanf("%d", &n), n != 0)
	{
		for(int i = 0; i < n; i++)
		{
			scanf("%lf%lf%lf%lf", &lines[i][0].x, &lines[i][0].y, &lines[i][1].x, &lines[i][1].y);
			ison[i] = false;
		}
		bool init = false;
		printf("Top sticks:");
		for(int i = 0; i < n; i++)
		{
			for(int j = i + 1; j < n; j++)
			{
				if(isIntesect(lines[i][0], lines[i][1], lines[j][0], lines[j][1]))
				{
					ison[i] = true;
					break;
				}
			}
			if(!ison[i])
			{
				if(init)
					printf(",");
				init = true;
				printf(" %d", i+1);
			}
		}
		printf(".\n");
	}
	return 0;
}

密室是指定点p，依次判断p与金字塔四周所有点组成的线段与其他线段相交的次数，统计最小值。

#include
#include
#include
using namespace std;

#define PI acos(-1)
#define eps 1e-6

typedef struct
{
	double x, y;
} Point;

typedef struct
{
	double x, y, r;
} Circle;

typedef struct
{
	double a, b, c;
} Line;


bool same(Point& p1, Point& p2)
{
	return abs(p1.x-p2.x) < eps && abs(p1.y-p2.y) < eps;
}
bool same(double x, double y)
{
	return abs(x-y) < eps;
}

double crossMul(Point p0, Point p1, Point p2)
{
	return (p2.x - p0.x) * (p1.y - p0.y) - (p1.x - p0.x) * (p2.y - p0.y);
}

//判断两线段是否相交(不包括一个端点在另一个上面）
bool isIntesect(Point s1, Point e1, Point s2, Point e2)
{
	return max(s1.x, e1.x) >= min(s2.x, e2.x) && max(s2.x, e2.x) >= min(s1.x, e1.x) && max(s1.y, e1.y) >= min(s2.y, e2.y) && max(s2.y, e2.y) >= min(s1.y, e1.y) && crossMul(s1, e1, s2)*crossMul(s1,e2, e1) > 0 && crossMul(s2, e2, s1)*crossMul(s2,e1, e2) > 0;
}

int main()
{
	int n, min_count = INT_MAX, cur_count;
	Point points[35][2], p, p0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%lf%lf%lf%lf", &points[i][0].x, &points[i][0].y, &points[i][1].x, &points[i][1].y);
	}
	points[n][0].x = 0; points[n][0].y = 0; points[n][1].x = 100; points[n][1].y = 0; n++;
	points[n][0].x = 0; points[n][0].y = 0; points[n][1].x = 0; points[n][1].y = 100; n++;
	points[n][0].x = 0; points[n][0].y = 100; points[n][1].x = 100; points[n][1].y = 100; n++;
	points[n][0].x = 100; points[n][0].y = 0; points[n][1].x = 100; points[n][1].y = 100; n++;
	scanf("%lf%lf", &p.x, &p.y);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			p0 = points[i][j];
			cur_count = 0;
			for(int k = 0; k < n; k++)
			{
				if(k != i)
				{
					if(isIntesect(p, p0, points[k][0], points[k][1]))
						cur_count++;
				}
			}
			if(cur_count < min_count)
				min_count = cur_count;
		}
	}
	printf("Number of doors = %d\n", min_count+1);
	return 0;
}