CF 18A(近似直角三角形判断+向量直角公式+switch+istream&(..&P a))

Posted on 22 1 月, 2013 by nike0good

判断一个格点三角形是直角三角形,近似直角三角形,还是都不是.

Hint:近似直角三角形是指把一个三角形的一个点移动1个单位长度(移动后仍为格点三角形)，其能变成直角三角形的非直角三角形

Input

x₁, y₁, x₂, y₂, x₃, y₃ 表示3点坐标（都在格点上），不超过
100.

Output

I直角三角形输出 RIGHT,

近似直角三角形输出 ALMOST, 都不是输出 NEITHER.

Sample test(s)

input
0 0 2 0 0 1

output
RIGHT

input
2 3 4 5 6 6

output
NEITHER

input
-1 0 2 0 0 1

output
ALMOST

各种判断…

注意格点三角形在移动完可能出现点重合（0向量）

仍满足向量直角公式a X b
= |a||b|

以及switch-case-default的用法。

△：default打错不会提示.

PS:istream& operator<<的重载中输入的struct 如果不加&，是读不进的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cmath>
using namespace std;
struct P
{
	int x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin;	}
	void move(int d)
	{
		if (d==1) x++;
		if (d==-1) x--;
		if (d==2) y++;
		if (d==-2) y--;
		return;
	}
}a[3];
struct V
{
	int x,y;
	V(){}
	V(int _x,int _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend int operator*(V a,V b){return a.x*b.y-a.y*b.x;}
	int dis2(){return x*x+y*y;	}
	friend bool right_angle(V a,V b){return pow(a*b,2)==a.dis2()*b.dis2();	}
}c[3];
void res_c()
{
	for (int i=0;i<3;i++) c[i]=V(a[i],a[(i+1)%3]);
}
bool is_r_trangle()
{
	res_c();
	for (int i=0;i<3;i++) if (!c[i].dis2()) return 0;
	for (int i=0;i<2;i++)
		for (int j=i+1;j<=2;j++) if (right_angle(c[i],c[j])) {/*cout<<i<<' '<<j<<endl;*/return 1;}
	return 0;
}
int solve()
{
	if (is_r_trangle()) return 1;
	for (int i=0;i<3;i++)
	{
		for (int j=-2;j<=2;j++)
		{
			if (j==0) continue;
			a[i].move(j);
			if (is_r_trangle()){/*cout<<i<<' '<<j<<endl;*/ return 2;}
			a[i].move(-j);
		}
	}
	return 0;
}
int main()
{
	for (int i=0;i<3;i++) cin>>a[i];

	switch (solve())
	{
		case 1:cout<<"RIGHT";break;
		case 2:cout<<"ALMOST";break;
		default:cout<<"NEITHER";
	}
	cout<<endl;

	return 0;
}

POJ 2398(二分点集)

Posted on 22 1 月, 2013 by nike0good

Language:

Toy Storage

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 8137		Accepted: 3848

Description

在长方形 (x1,y1) (x2,y2) 中有n块板（保证与上下边相交），和m个点。

现给出板和点的位置，求拥有相同点数的区域数、

Input

多组数据.每组数据开头为 n m x1 y1 x2 y2. n (0 < n <= 5000) m (0 < m <= 5000). (x1,y1)为左上角坐标 , (x2,y2)为右下角坐标.

接下来 n 行有2个数 Ui Li,表示第i块板为 (Ui,y1) (Li,y2). （保证两两不交）.

接下来m 行为点的坐标 Xj Yj （保证不在板上）

数据以 0 结束.

Output

每组数据给出同点数的区域数

点数: 区域数

…(点数1→n，区域数为0不输出)

请按这个格式输出。

每组数据开头输出“Box”。

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
0

Sample Output

Hint

落在长方形边上的点也算.

Source

Rocky Mountain 2003

基本同POJ 2318

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (1000+10) //Board
#define MAXM (1000+10) //Toy
struct P
{
	double x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin;	}
}a[MAXM];
struct V
{
	double x,y;
	P s;
	V(){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y),s(a){}
	friend int operator*(const V a,const V b)
	{
		return a.x*b.y-a.y*b.x;
	}
}c[MAXN];
int n,m,x1,y1,x2,y2,f[MAXM];
int cmp(V a,V b)
{
	return a.s.x<b.s.x;
}
void binary(int L,int R,int l,int r)
{
	if (R-L==1)
	{
		f[r-l+1]++;
		return;
	}
	int i=l,j=r,m=(l+r)>>1;
	V &M=c[(L+R)>>1];
	do
	{
		while (i<=r&&V(M.s,a[i])*M<0) i++;
		while (j>=l&&V(M.s,a[j])*M>0) j--;
		if (i<=j) {swap(a[i],a[j]);i++;j--;	}
	}while (i<=j);

	i--;j++;
	binary(L,(L+R)>>1,l,i);
	binary((L+R)>>1,R,j,r);

}
int main()
{
//	freopen("poj2398.in","r",stdin);

	while (scanf("%d%d",&n,&m)==2)
	{
		cout<<"Boxn";
		memset(f,0,sizeof(f));
		cin>>x1>>y2>>x2>>y1;
		for (int i=1;i<=n;i++)
		{
			int u,l;
			cin>>u>>l;
			c[i]=V(P(l,y1),P(u,y2));
		}
		c[0]=V(P(x1,y1),P(x1,y2));c[n+1]=V(P(x2,y1),P(x2,y2));
		sort(c+1,c+1+n,cmp);
		for (int i=1;i<=m;i++) cin>>a[i];
		binary(0,n+1,1,m);
		for (int i=1;i<=m;i++)
			if (f[i]) cout<<i<<": "<<f[i]<<endl;
	}
	return 0;
}

POJ 2318(点集二分)

Posted on 22 1 月, 2013 by nike0good

Language:

TOYS

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 8137		Accepted: 3848

Description

在长方形 (x1,y1) (x2,y2) 中有n块板（保证与上下边相交），和m个点。

现给出板和点的位置，求各区域点数、

Input

多组数据.每组数据开头为 n m x1 y1 x2 y2. n (0 < n <= 5000) m (0 < m <= 5000). (x1,y1)为左上角坐标 , (x2,y2)为右下角坐标.

接下来 n 行有2个数 Ui Li,表示第i块板为 (Ui,y1) (Li,y2). （保证两两不交，且板从左至右给出）.

接下来m 行为点的坐标 Xj Yj （保证不在板上）

数据以 0 结束.

Output

每组数据给出各区域点数（最左边区域编号0）

区域编号: 点数

…(区域编号0→n)

请按这个格式输出。

不同组数据间输出一空行。

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
0

Sample Output

Hint

落在长方形边上的点也算.

Source

Rocky Mountain 2003

直接枚举点超时，

所以枚举中间那块板，二分查找（注意Qsort性质,[1, i-1] 和 [ j+1,n]即为所求范围）

但是由于中间那块板并不“计入点集”，所以 i 和 j 可能越界，要特判。

由于用int会乘越界（这题没给范围），所以稳妥的用double.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (5000+10) //Board
#define MAXM (5000+10) //Toy
struct P
{
	double x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin;	}
}a[MAXM];
struct V
{
	double x,y;
	P s;
	V(){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y),s(a){}
	friend int operator*(const V a,const V b)
	{
		return a.x*b.y-a.y*b.x;
	}
}c[MAXN];
int n,m,x1,y1,x2,y2;
void binary(int L,int R,int l,int r)
{
	if (R-L==1)
	{
		cout<<L<<": "<<r-l+1<<endl;
		return;
	}
	int i=l,j=r,m=(l+r)>>1;
	V &M=c[(L+R)>>1];
	do
	{
		while (i<=r&&V(M.s,a[i])*M<0) i++;
		while (j>=l&&V(M.s,a[j])*M>0) j--;
		if (i<=j) {swap(a[i],a[j]);i++;j--;	}
	}while (i<=j);

	i--;j++;
	binary(L,(L+R)>>1,l,i);
	binary((L+R)>>1,R,j,r);

}
int main()
{
//	freopen("poj2318.in","r",stdin);
	scanf("%d%d",&n,&m);
	while (1)
	{
		cin>>x1>>y2>>x2>>y1;
		for (int i=1;i<=n;i++)
		{
			int u,l;
			cin>>u>>l;
			c[i]=V(P(l,y1),P(u,y2));
		}
		c[0]=V(P(x1,y1),P(x1,y2));c[n+1]=V(P(x2,y1),P(x2,y2));
		for (int i=1;i<=m;i++) cin>>a[i];
		binary(0,n+1,1,m);
		if (scanf("%d%d",&n,&m)==2) cout<<endl; else break;
	}
	return 0;
}

POJ 1228(稳定凸包)

Posted on 22 1 月, 2013 by nike0good

Language:

Grandpa's Estate

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 8990		Accepted: 2383

Description

Kamran the Believer继承了祖母的一个凸多边形庄园. 庄园外围用绳子和木桩围起. 但一些绳子和木桩缺失了.帮忙看一下用剩余木桩围起的庄园是否是稳定凸包（即剩下的钉子能确定一个唯一的凸包）.

Input

第一行一个数据组数 t (1 <= t <= 10).

对于每组数据，第一行为 n (1 <= n <= 1000) 表示木桩数. 接下来n行，每行为木桩坐标(x,y)，保证整数.

Output

对每组数据输出YES 或 NO ，表示其是否稳定.

Sample Input

Sample Output

NO

Source

Tehran 2002 Preliminary

要想让一个凸包稳定，当且仅当凸包上任意一条边有3个以上的木桩（包括端点）

证明：

只要在建完凸包后，枚举，边上的第3点即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXT (10+10)
#define MAXN (1000+10)
//#define sqr( x ) (x*x)
int sqr(int x){return x*x;}
struct P
{
	int x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream &cin,P &a)
	{
		cin>>a.x>>a.y;return cin;
	}
	friend double dis(P a,P b)
	{
		return sqrt(double(sqr(a.x-b.x)+sqr(a.y-b.y)));
	}
}a[MAXN];
struct V
{
	int x,y;
	V(){}
	V(int _x,int _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend int operator*(V a,V b)
	{
		return a.x*b.y-a.y*b.x;
	}
};
int cmp(P A,P B)
{
	int temp=V(a[1],A)*V(a[1],B);
	if (temp>0) return 1;
	else if (temp==0&&dis(a[1],A)<dis(a[1],B)) return 1;
	else return 0;
}
int t,n,st[MAXN];
bool solve()
{
	int size=1;st[0]=1;
	st[1]=1;
	int j=2;
	while (j<=n)
	{
		if (size<2||V(a[st[size-1]],a[st[size]])*V(a[st[size]],a[j])>0)
		{
			st[++size]=j++;
		}
		else size--;
	}
	a[++n]=a[1];
	st[++size]=n;

	for (int i=1;i<size;i++)
	{
	/*
		int k=st[i-1]+1;
		for (;k<st[i+1];k++)
			if (k!=st[i]&&V(a[st[i]],a[st[i+1]])*V(a[st[i]],a[st[k]])==0) break;
		if (k==st[i+1]) return 0;
	*/
		int k=1;
		for (;k<n;k++)
			if (k!=st[i]&&k!=st[i+1]&&V(a[st[i]],a[st[i+1]])*V(a[st[i]],a[k])==0) break;
		if (k==n) return 0;
	}
	return size>=4;
}
int main()
{
//	freopen("poj1228.in","r",stdin);
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++) cin>>a[i];
		if (n<6)
		{
			cout<<"NOn";
			continue;
		}
		int p=1;
		for (int i=2;i<=n;i++) if (a[i].x<a[p].x||(a[i].x==a[p].x)&&(a[i].y<a[p].y)) p=i;
		swap(a[1],a[p]);
		sort(a+2,a+1+n,cmp);
//		cout<<dis(P(0,0),P(1,0))<<dis(P(0,0),P(1,0));
		if (solve()) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}

nike0good

有所作为是人生的最高境界

Daily Archives: 22 1 月, 2013

CF 18A(近似直角三角形判断+向量直角公式+switch+istream&(..&P a))

POJ 2398(二分点集)

POJ 2318(点集二分)

POJ 1228(稳定凸包)

2013 年 1 月
一	二	三	四	五	六	日
	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