Tag Archives: 计算几何

POJ 2318(点集二分)

Posted on by
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

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

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 2187(凸包GrahamScan扫描+极角排序+平面最远点对）

Posted on by
Language:
平面最远点对
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 22454   Accepted: 6868

Description

求 N (2 <= N <= 50,000) 个点平面最远点对距离的平方. 

Input

* 第1行:N 

接下来每行为点的坐标 x 和 y ,(x,y)(-10,000<=x,y<=10,000的整数). 

Output

输出一行，为平面最远点对距离平方. 

Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

2

Hint

(0, 0) a到 (1, 1) 距离平方为 2 

Source

USACO 2003 Fall

凸包模版题：

先用GrahamScan扫描求凸包，显然最远点对在凸包上。


极角排序：

按照逆时针顺序给平面上的点集到一个点的距离排序，使得排序后所有点正好绕这个点一圈.（按距离远近从小到大排

思路：


GrahamScan扫描：







大致如此.


另补：

该题小Bug-有可能所有点在一条直线上。

这样也能求出：

Ex:

a序列（-1，0） （0，0)    （4，0）   （9，0）

则st序列重复如下操作：

（-1，1），（0，0）入队。

（4，0）入队，不左拐->（0，0）出队

队列元素<2 （4，0）入队

……


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (50000+10)
double sqr(double x){return x*x;}
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
}a[MAXN],st[MAXN];
int dis2(P A,P B)
{
	return sqr(A.x-B.x)+sqr(A.y-B.y);
}
double dis(P A,P B)
{
	return sqrt(double(dis2(A,B)));
}
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P A,P B):x(B.x-A.x),y(B.y-A.y){}
};
double operator*(V a,V b)
{
	return a.x*b.y-a.y*b.x;
}
int cmp(P A,P B) //1:a>b 0:a<=b
{
	double tmp=V(a[1],A)*V(a[1],B);
	if (tmp>0) return 1;
	else if (tmp==0) return (-(dis(a[1],A)-dis(a[1],B))>0)?1:0;
	else return 0;
}
int n;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	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;
	if (p>1) swap(a[p],a[1]);
	sort(a+2,a+1+n,cmp);

	int size=1;
	st[1]=a[1];
	for (int i=2;i<=n;)
		if (size<2||V(st[size-1],st[size])*V(st[size],a[i])>0)
			st[++size]=a[i++];
		else size--;

	int ans=0;
	for (int i=1;i<size;i++)
		for (int j=i+1;j<=size;j++)
			ans=max(ans,dis2(st[i],st[j]));
	cout<<ans<<endl;


	return 0;
}







POJ 3304(线段与直线相交）

Posted on by
Language:
Segments
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 7144   Accepted: 2135

Description

在平面内给 n 条线段，问是否存在一条直线，使得所有线段在这条直线上的投影有公共点.

Input

第一行输入 T 表示数据组数，接下来 T 组数据每组第一行一个整数 n ≤ 100 表示线段数，接下来n 行每行有 x1 y1 x2 y2 表示线段的两个端点 (x1, y1) 和 (x2, y2)
.

Output

对于每组数据,如果存在这样的直线，输出一行 "Yes!", 否则输出 "No!" . 精度|a - b| < 10-8.

Sample Input

3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0

Sample Output

Yes!
Yes!
No!

Source

Amirkabir University of Technology Local Contest 2006


显然该题可转换为是否存在一条直线与所有线段相交。（如果存在，则通过移动选转，使其过的2个线段的端点）

需要特判2个点如果相同，那么连不成线段，因为最后叉积算出来为0.


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define eps 1e-8
#define MAXN (200+10)
struct P
{
	long double x,y;
	P(){}
	P(long double _x,long double _y):x(_x),y(_y){}
}a[MAXN*2];
struct V
{
	long double x,y;
	V(){}
	V(long double _x,long double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
};
struct S
{
	P A,B;
	S(P _A,P _B):A(_A),B(_B){}
	S(){}
};
double operator*(V a,V b)
{
	return a.x*b.y-b.x*a.y;
}
bool corr(P A,P B,P C,P D)
{
	V AB=V(A,B),AC=V(A,C),AD=V(A,D);
	return ((AC*AB)*(AB*AD)>-eps);
}
bool fabs (double a,double b)
{
	if (abs(a-b)<eps) return 1 ;return 0;
}
bool fabs(P A,P B)
{
	return (fabs(A.x,B.x)&&fabs(A.y,B.y));
}
int t,n;
int main()
{
//	freopen("poj3304.in","r",stdin);
	scanf("%d",&t);
	while (t--)
	{
		cin>>n;
		bool flag=0;
		for (int i=1;i<=2*n;i++) cin>>a[i].x>>a[i].y;
		for (int i=1;i<2*n&&!flag;i++)
		{
			for (int j=i+1;j<=2*n;j++)
			{
				if (fabs(a[i],a[j])) continue;
				S l=S(a[i],a[j]);
				int k;
				for (k=1;k<=n;k++)
				{
					if (!corr(l.A,l.B,a[k*2-1],a[k*2])) break;
				//	cout<<k;
				}
				if (k==n+1) {cout<<"Yes!n"; flag=1;break;}
			}
		}

		if (!flag) cout<<"No!n";


	}
	return 0;
}


POJ 1269(直线的交点)

Posted on by
Language:
Intersecting Lines
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 7657   Accepted: 3510

Description

求两条直线相交部分，给出的坐标的范围在 -1000 到 1000 之间且为整数. 

Input

第一行为数据组数 N≤10 
接下来N行，每行为x1y1x2y2x3y3x4y4.表示第一条直线过 (x1,y1) 和 (x2,y2) ，第二条过 (x3,y3) 和 (x4,y4). 保证直线能被确定.

Output

输出 N+2 第一行输出INTERSECTING LINES OUTPUT. 接下来每行输出相交部分 none, line, 或 point x y(保留2位小数). 最后1行输出 "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

模板如下：

注意* 表示叉积

这题涉及已知相交，线段跨立求交点

异侧情况：


同侧情况：




#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define eps 1e-8
double sqr(double x) {return x*x;}
struct P
{
	double x,y;
	P(double _x,double _y):x(_x),y(_y){}
	P(){}
	double dis()
	{
		return sqrt(sqr(x)+sqr(y));
	}
};
struct V
{
	double x,y;
	V(double _x,double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	V(){}
	const double dis()
	{
		return sqrt(sqr(x)+sqr(y));
	}
};
P operator+(const P a,const V b)
{
	return P(a.x+b.x,a.y+b.y);
}
V operator*(const double a,const V b)
{
	return V(a*b.x,a*b.y);
}
double operator*(const V a,const V b)
{
	return a.x*b.y-b.x*a.y;
}
P jiao_dian(const V a,V b,const V c,const V CD,const P C)
{
	double d;
	d=b.dis();
	double s1=a*b,s2=b*c;
	double k=s1/(s1+s2);
	return C+k*CD;
}
bool equal(const double a,const double b)
{
	if (abs(a-b)<eps) return 1;return 0;
}
int n;
int main()
{
//s	freopen("poj1269.in","r",stdin);
	cout<<"INTERSECTING LINES OUTPUT"<<endl;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		double x1,y1,x2,y2,x3,y3,x4,y4;
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
		P A=P(x1,y1),B=P(x2,y2),C=P(x3,y3),D=P(x4,y4);
		V AB=V(A,B),AC=V(A,C),AD=V(A,D),CD=V(C,D);
		if (equal((AB*CD),0))
		{
			if (equal((AC*AD),0)) cout<<"LINEn";
			else cout<<"NONEn";
		}
		else
		{
			P p=jiao_dian(AC,AB,AD,CD,C);
			cout.setf(ios::fixed);
			cout.precision(2);
			cout<<"POINT "<<p.x<<' '<<p.y<<endl;
		}
	}
	cout<<"END OF OUTPUT"<<endl;
	return 0;
}

求面积 （坐标叉积公式+凹多边形面积-坐标公式）

Posted on by

求面积（AREA）

给出一个简单多边形(没有缺口)，它的边要么是垂直的，要么是水平的。要求计算多边形的面积。

多边形被放置在一个X-Y的卡笛尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数(因此多边形的面积也为整数)。

 

输入

输入文件第一行给出多边形的顶点数n(n≤100)。接下来的几行每行给出多边形一个顶点的坐标值X和Y(都为整数并且用空格隔开)。顶点按逆时针方向逐个给出。并且多边形的每一个顶点的坐标值-200≤x,y≤200。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。

 

输出

输出文件仅有一行包含一个整数，表示多边形的面积。

 

样例

AREA.IN

10

0 0

4 0

4 1

3 1

3 3

2 3

2 2

1 2

1 3

0 3

 

AREA.OUT

9

叉积公式 A X B= x1y2-x2y1=S(平行四边形）=2S(三角形）=2*|a|*|b|*sinaC




#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN (100+10)
class _vector
{
public:
	int x,y;
	_vector():x(0),y(0){}
	_vector(int _x,int _y):x(_x),y(_y){}
	friend int operator*(const _vector a,const _vector b)
	{
		return a.x*b.y-a.y*b.x;
	}

}node[MAXN];

istream& operator>>(istream& in,_vector& a)
{
	in>>a.x>>a.y;
	return in;
}
int n;
int main()
{
	freopen("area.in","r",stdin);
	freopen("area.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) cin>>node[i];
	node[n+1]=node[1];
	int ans=0;
	for (int i=1;i<=n;i++)
		ans+=node[i]*node[i+1];
	ans=abs(ans);

	printf("%dn",int(round(double(ans)/2)));
//	while (1);
	return 0;


}

POJ 3575(计算几何与二分-无尽的小数处理）

Posted on by

这题 写了将近半个月……总是在D各种Bug

总的说来-这题最难应该是在精度处理上

1

1

0 0 1

这组数据过了就说明精度处理差不多了……

Program kingdom;
const
   maxn=100;
   maxm=100;
   le=0.000000001;
type
   circle=record
            x,y,r:double;
          end;
var
   s:array[1..maxn,1..1000] of circle;
   n,i,j,k:longint;
   m:array[1..maxn] of longint;
   ans:array[1..maxn,1..4] of double;
   wanted:array[1..maxn] of double;
   b:array[1..maxn] of boolean;
   l,r:double;
function arccos(cosa:double):double;
var
   sina,tana:double;
begin
   if cosa=0 then exit(pi/2);

   sina:=sqrt(1-sqr(cosa));
   tana:=sina/cosa;
   exit(arctan(tana));

end;
function min(a,b:double):double;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:double):double;
begin
   if a>b then exit(a) else exit(b);
end;

function sector(a,r:double):double;
begin
   exit(a*r*r/2);
end;
function triangle(a,r:double):double;
begin
   exit(sin(a)*r*r/2);
end;
function inlside(s:circle;l:double):boolean;
begin
   if (s.x-s.r>l) or (abs(s.x-s.r-l)<le) then exit(true) else exit(false);
end;
function inrside(s:circle;r:double):boolean;
begin
   if (s.x+s.r<r) or (abs(s.x+s.r-r)<le) then exit(true) else exit(false);
end;


function intarea(s:circle;l,r:double):double;
var
   i,j:longint;
   a,a2,s1,s2,s3,s4:double;
   bl,br:boolean;
begin
   if (r<s.x-s.r) or (s.x+s.r<l) then exit(0);
   if (s.x<=l) then
   begin
      a:=arccos((l-s.x)/s.r)*2;
      if (abs(s.x-l)<le) then s1:=0
      else s1:=triangle(a,s.r);
      s2:=sector(a,s.r);


      if s.x+s.r>r then
      begin
         a:=arccos((r-s.x)/s.r)*2;
         s3:=sector(a,s.r);
         s4:=triangle(a,s.r);
         s2:=s2-(s3-s4);

      end;
      exit(s2-s1);
   end
   else
   if (s.x>=r) then
   begin
      a:=arccos((s.x-r)/s.r)*2;
      if (abs(s.x-r)<le) then s1:=0
      else s1:=triangle(a,s.r);
      s2:=sector(a,s.r);

      if s.x-s.r<l then
      begin
         a:=arccos((s.x-l)/s.r)*2;
         s3:=sector(a,s.r);
         s4:=triangle(a,s.r);
         s2:=s2-(s3-s4);


      end;
      exit(s2-s1);

   end
   else
   begin
      bl:=inlside(s,l);
      br:=inrside(s,r);
      if bl and br then exit(pi*s.r*s.r);
      if bl and not(br) then
      begin
         a:=arccos((r-s.x)/s.r)*2;
         s3:=sector(a,s.r)-triangle(a,s.r);
         exit(pi*s.r*s.r-s3);
      end;
      if not(bl) and br then
      begin
         a:=arccos((s.x-l)/s.r)*2;
         s3:=sector(a,s.r)-triangle(a,s.r);
         exit(pi*s.r*s.r-s3);
      end;



      a:=arccos((s.x-l)/s.r)*2;

      a2:=arccos((r-s.x)/s.r)*2;
      s1:=sector(2*pi-a-a2,s.r);
      s2:=triangle(a,s.r)+triangle(a2,s.r);
      exit(s1+s2);



   end;



end;
function place(k:longint;l,r:double):boolean;
var
   tot:double;
   i,j:longint;
begin
   tot:=0;
   for j:=1 to m[k] do
   begin
         tot:=tot+intarea(s[k,j],l,r);
   end;
//   writeln(tot*n,' ',wanted[k]*pi);

   if (abs(tot*n-wanted[k]*pi)<le) then exit(true);
   if (tot*n<(wanted[k]*pi)) then exit(false) else exit(true);
end;
function bsearch(r1,r2:double):double;
var
   m:double;
   i,j,k,num:longint;
   flag:boolean;
begin
   for k:=1 to 60 do
   begin
      flag:=false;
      m:=(r1+r2)/2;
      for i:=1 to n do
         if not b[i] then
         begin
            flag:=flag or place(i,l,m);
            if flag then
            begin
               num:=i;
               break;
            end;
         end;
      if flag then r2:=m else r1:=m;
   end;

   b[num]:=true;
   ans[num,1]:=l;
   ans[num,2]:=r1;

   exit(r1);


end;
begin
  { assign(input,'kingdom.in');
   reset(input);
  } r:=-10000;
   l:=10000;
   read(n);
   fillchar(b,sizeof(b),false);
   fillchar(wanted,sizeof(wanted),0);
   for i:=1 to n do
   begin
      read(m[i]);
      for j:=1 to m[i] do
      begin
         read(s[i,j].x,s[i,j].y,s[i,j].r);
 //        writeln(s[i,j].x,s[i,j].y,s[i,j].r);

         r:=max(r,s[i,j].x+s[i,j].r);
         l:=min(l,s[i,j].x-s[i,j].r);
         wanted[i]:=wanted[i]+sqr(s[i,j].r);

      end;
   end;
   r:=r+1;

   for i:=1 to n do
      l:=bsearch(l,r);

   for i:=1 to n do
   begin
      writeln('4');
      writeln(ans[i,1]:7:7,' 3000');
      writeln(ans[i,1]:7:7,' -3000');
      writeln(ans[i,2]:7:7,' -3000');
      writeln(ans[i,2]:7:7,' 3000');
   end;




//   close(input);
end.