首页 > 其他分享 >POJ 2588(解析几何+并查集)

POJ 2588(解析几何+并查集)

时间:2022-10-25 12:35:51浏览次数:64  
标签:begin fillchar end sqr 查集 father 2588 POJ sizeof


题目就是早从左到右的路

注意输入的实数

这题图画好就行,别像我一开始把图弄反就成

从上开始找,若找到一个与下边界相邻的就无解,找到与左边相邻的记圆与左边界相交的下边的点(相当于左上角挖去一块),右边同理。


Program snake;
const
maxn=1000;
var
n,i,j:longint;
x,y,r,lc,rc:array[1..maxn] of double;
maxl,maxr:double;
father:array[1..maxn] of longint;
b,up,down,left,right:array[1..maxn] of boolean;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
Procedure union(x,y:longint);
begin
father[father[x]]:=father[father[y]];
end;
function distance(i,j:longint):double;
begin
exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));
end;
function dis(x1,y1,x2,y2:double):double;
begin
exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;

begin
fillchar(b,sizeof(b),false);
fillchar(up,sizeof(up),false);
fillchar(down,sizeof(down),false);
fillchar(left,sizeof(left),false);
fillchar(right,sizeof(right),false);
fillchar(lc,sizeof(lc),0);
fillchar(rc,sizeof(rc),0);
maxl:=1000;maxr:=1000;

read(n);
for i:=1 to n do
begin
read(x[i],y[i],r[i]);
father[i]:=i;
for j:=1 to i-1 do
if distance(i,j)<r[i]+r[j] then
if getfather(i)<>getfather(j) then
union(i,j);
if (y[i]<r[i]) then down[i]:=true;
if (y[i]+r[i]>1000) then up[i]:=true;
if (x[i]<r[i]) then
begin
left[i]:=true;
lc[i]:=y[i]-sqrt(sqr(r[i])-sqr(x[i]));
end;
if (x[i]+r[i]>1000) then
begin
right[i]:=true;
rc[i]:=y[i]-sqrt(sqr(r[i])-sqr(1000-x[i]));
end;

end;
for i:=1 to n do
if (up[i]) and not(b[i]) then
begin
for j:=1 to n do
if father[i]=father[j] then
begin
b[j]:=true;
if (down[j]) then
begin
writeln('Bill will be bitten.');
halt;
end;
if left[j] then
begin
if lc[j]<maxl then maxl:=lc[j];

end;
if right[j] then
begin
if rc[j]<maxr then maxr:=rc[j];
end;


end;
end;
writeln('Bill enters at (0.00, ',maxl:2:2,') and leaves at (1000.00, ',maxr:2:2,').');




end.



标签:begin,fillchar,end,sqr,查集,father,2588,POJ,sizeof
From: https://blog.51cto.com/u_15724837/5794482

相关文章

  • POJ 3844(同余)
    果断同余……D[j]-D[i] mod k=0D[j]=D[i]求有多少相等数对,用队列O(n)ProgramP3844;constmaxn=50000;maxd=1000000;varans,t,f,n,i,j:longint;d:array[0........
  • POJ 3122(二分答案)
    二分答案……Programpie;constlef=0.00001;vart,n,f,i,j:longint;r:array[1..10000]oflongint;s:array[1..10000]ofdouble;maxs:double;procedures......
  • POJ 3842(质数判断)
    7!=5040所以这题直接求质数比打一千万的表都快这提高诉我们阶乘其实不算大&看(算)清数据规模Programcc;varn,t,len,i,j,ans:longint;s:string;b:array[0..9]oflong......
  • POJ 1125(Floyd)
    裸FloydProgramP1125;constmaxn=100;maxedge=10;NULL=-2139062144;varn,i,j,k,m,v,t,ans:longint;f:array[1..maxn,1..maxn]oflongint;functionmax(a,b:......
  • POJ 1700(过河问题)
    玩过《雷顿》就知道这题可以贪心小等于2人:1,2->3人时:1,3->1<-1,2->1<-否则:1,2->2<-max1,max2->1<-OR:1,max1->1<-2,max2->2<-于是数据规模-2ProgramP1700;vart,n,i,j:long......
  • POJ 3264(STRMQ)
    forj:=1toln(n)/ln(2)  fori:=1ton-(1shlj)+1do    f[i,j]:=min(f[i,j-1],f[i+(1shl(j-1),j-1];f[l,r]:=min(f[l,j],f[r-(1shlj)+1,j];j=ln(r-l+1......
  • POJ 3748(C++的16进制读法 %x)
    P党写几小时的程序C++才几行……首先P的位运算有上限2^30此时即便是int64也会因为补码坑死人的到1shl31时 int64是负数故这个时候不能shr为多出好多位造成以......
  • POJ 2185(最大平铺矩阵)
    DefaultMilkingGridDescription(1<=R<=10,000) *C (1<=C<=75) 的矩阵,求它的最大平铺矩阵,不够的地方可部分平铺,但不可重叠。Input......
  • POJ 3661(贝茜晨练)
    经典Dp,果断记忆化……#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<functional>usingnamespacestd;#defineMAXN10000+10#defineM......
  • POJ 3575(计算几何与二分-无尽的小数处理)
    这题写了将近半个月……总是在D各种Bug总的说来-这题最难应该是在精度处理上11001这组数据过了就说明精度处理差不多了……Programkingdom;constmaxn=100;maxm=10......