HDOJ 1558 Segment set
これは比較的に簡単な計算幾何学に加えて収集した問題で、私は計算幾何学の問題をめったにしません.この問題はWrongで3回もありました.主に問題の中のtest caseの間に空行があるはずです.最後のcaseには空行がありません.この問題は主に絵の線分が交差しているかどうかを判断し、交差すると相が1つの集合に並ぶ.
コード:
コード:
#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;
#define exp 1e-6
struct Point
{
double x,y;
};
struct Segment
{
Point a,b;
} seg[1005];
int f[1005],num[1005];
int Cross(Point a,Point b,Point c)
{
double t=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if( fabs(t)<exp)
return 0;
return ( t>0 ? 1:-1);
}
bool Judge(Point a,Point b,Point c)
{
if( a.x>=min(b.x,c.x) && a.x<=max(b.x,c.x) && a.y>=min(b.y,c.y) && a.y<=max(b.y,c.y) )
return true;
return false;
}
bool SegCross(Segment s1,Segment s2)
{
int d1=Cross(s1.a,s1.b,s2.a);
int d2=Cross(s1.a,s1.b,s2.b);
int d3=Cross(s2.a,s2.b,s1.a);
int d4=Cross(s2.a,s2.b,s1.b);
if( (d1^d2)==-2&&(d3^d4)==-2 || ( d1==0&&Judge(s2.a,s1.a,s1.b) )
|| (d2==0&&Judge(s2.b,s1.a,s1.b)) || (d3==0&&Judge(s1.a,s2.a,s2.b))
|| (d3==0&&Judge(s1.b,s2.a,s2.b)) )
return true;
return false;
}
void Init(int n)
{
memset(seg,0,sizeof(seg));
for(int i=0; i<n; i++){
f[i]=i;
num[i]=1;
}
}
int Find(int x)
{
if( x!=f[x])
f[x]=Find(f[x]);
return f[x];
}
void Union(int i,int j)
{
i=Find(i);
j=Find(j);
if( i!=j){
f[i]=j;
num[j]+=num[i];
}
}
int main()
{
int t,id,k,n;
char ch;
cin>>t;
while( t--){
k=0;
cin>>n;
Init(n);
while( n--){
cin>>ch;
if( ch=='Q'){
cin>>id;
cout<<num[Find(id-1)]<<endl;
}
else{
cin>>seg[k].a.x>>seg[k].a.y>>seg[k].b.x>>seg[k].b.y;
for(int i=0; i<k; i++){
if( SegCross(seg[i],seg[k])){ //
Union(i,k);
}
}
++k;
}
}
if( t)
cout<<endl;
}
system("pause");
return 0;
}