链接

繁琐。

处理出来所有的线段,再判断相交。

对于正方形的已知对角顶点求剩余两顶点 (列出4个方程求解)

p[].x=(p[].x+p[].x+p[].y-p[].y)/;
p[].y=(p[].y+p[].y+p[].x-p[].x)/;
p[].x=(p[].x+p[].x-p[].y+p[].y)/;
p[].y=(p[].y+p[].y-p[].x+p[].x)/;
 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define N 600
#define LL long long
#define INF 0xfffffff
#define zero(x) (((x)>0?(x):-(x))<eps)
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
map<string,int>f;
vector<int>ed[];
int g;
struct point
{
double x,y;
point(double x=,double y=):x(x),y(y) {}
} p[];
typedef point pointt;
pointt operator -(point a,point b)
{
return pointt(a.x-b.x,a.y-b.y);
}
struct line
{
pointt u,v;
int flag;
char c;
} li[N];
vector<line>dd[];
char s1[],s2[],s[];
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
point rotate(point a,double rad)
{
return point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
double dot(point a,point b)
{
return a.x*b.x+a.y*b.y;
}
double dis(point a)
{
return sqrt(dot(a,a));
}
double angle(point a,point b)
{
return acos(dot(a,b)/dis(a)/dis(b));
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
} double xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//判三点共线
int dots_inline(point p1,point p2,point p3)
{
return zero(xmult(p1,p2,p3));
} //判点是否在线段上,包括端点
int dot_online_in(point p,point l1,point l2)
{
return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
} //判两点在线段同侧,点在线段上返回0 int same_side(point p1,point p2,point l1,point l2)
{
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
} //判两线段相交,包括端点和部分重合 int intersect_in(point u1,point u2,point v1,point v2)
{
if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
}
void init(int kk,char c)
{
int i;
int k = c-'A';
if(kk==)
{
for(i = ; i <= ; i+=)
{
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
}
p[].x=(p[].x+p[].x+p[].y-p[].y)/;
p[].y=(p[].y+p[].y+p[].x-p[].x)/;
p[].x=(p[].x+p[].x-p[].y+p[].y)/;
p[].y=(p[].y+p[].y-p[].x+p[].x)/;
p[] = p[];
for(i = ; i < ; i++)
{
li[++g].u = p[i];
li[g].v = p[i+];
dd[k].push_back(li[g]);
}
}
else if(kk==)
{
for(i = ; i <= ; i++)
{
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
}
point pp = point((p[].x+p[].x),(p[].y+p[].y));
p[] = point(pp.x-p[].x,pp.y-p[].y);
//printf("%.3f %.3f\n",p[4].x,p[4].y);
p[] = p[];
for(i = ; i <= ; i++)
{
li[++g].u = p[i];
li[g].v = p[i+];
li[g].c = c;
dd[k].push_back(li[g]);
}
}
else if(kk==)
{
for(i = ; i <= ; i++)
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
li[++g].u = p[];
li[g].v = p[];
li[g].c = c;
dd[k].push_back(li[g]);
}
else if(kk==)
{
for(i = ; i <= ; i++)
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
p[] = p[];
for(i = ; i <= ; i++)
{
li[++g].u = p[i];
li[g].v = p[i+];
li[g].c = c;
dd[k].push_back(li[g]);
}
}
else if(kk==)
{
int n;
scanf("%d",&n);
for(i = ; i <= n ; i++)
scanf(" (%lf,%lf)",&p[i].x,&p[i].y);
p[n+] = p[];
for(i = ; i <= n ; i++)
{
li[++g].u= p[i];
li[g].v = p[i+];
li[g].c = c;
dd[k].push_back(li[g]);
}
}
} int main()
{
f["square"] = ;
f["rectangle"] = ;
f["line"] = ;
f["triangle"] = ;
f["polygon"] = ;
int i,j,k;
while(scanf("%s",s1)!=EOF)
{
if(s1[]=='.') break;
if(s1[]=='-') continue;
for(i = ; i < ; i++)
{
ed[i].clear();
dd[i].clear();
}
g = ;
k=;
scanf("%s",s2);
s[++k] = s1[];
init(f[s2],s1[]);
while(scanf("%s",s1)!=EOF)
{
if(s1[]=='-') break;
//cout<<s1<<endl;
scanf("%s",s2);
s[++k] = s1[];
init(f[s2],s1[]);
}
//cout<<g<<endl;
sort(s+,s+k+);
for(i = ; i <= k; i++)
{
int u,v;
u = s[i]-'A';
//cout<<u<<" "<<dd[u].size()<<endl;
for(j = i+; j <= k ; j++)
{
v = s[j]-'A';
int flag = ;
for(int ii = ; ii < dd[u].size() ; ii++)
{
for(int jj = ; jj < dd[v].size() ; jj++)
{
if(intersect_in(dd[u][ii].u,dd[u][ii].v,dd[v][jj].u,dd[v][jj].v))
{ flag = ;
break;
}
// if(u==5&&v==22)
// {
// output(dd[u][ii].u);
// output(dd[u][ii].v);
// output(dd[v][jj].u);
// output(dd[v][jj].v);
// }
}
if(flag) break;
}
if(flag)
{
ed[u].push_back(v);
ed[v].push_back(u);
}
}
}
for(i = ; i <= k; i++)
{
int u = s[i]-'A';
if(ed[u].size()==)
printf("%c has no intersections\n",s[i]);
else
{ sort(ed[u].begin(),ed[u].end());
if(ed[u].size()==)
printf("%c intersects with %c\n",s[i],ed[u][]+'A');
else if(ed[u].size()==)
printf("%c intersects with %c and %c\n",s[i],ed[u][]+'A',ed[u][]+'A');
else
{
printf("%c intersects with ",s[i]);
for(j = ; j < ed[u].size()- ; j++)
printf("%c, ",ed[u][j]+'A');
printf("and %c\n",ed[u][j]+'A');
}
}
}
puts("");
}
return ;
}

最新文章

  1. 背包九讲 &amp;&amp; 题目
  2. DataGridView 控件详细解说
  3. 【终极解决方案】为应用程序池“XXX”提供服务的进程在与 Windows Process Activation Service 通信时出现严重错误。该进程 ID 为“XXXX”。数据字段包含错误号。
  4. Synchronizing with Remote Repositories
  5. Heritrix源码分析(六) Heritrix的文件结构分析(转)
  6. 11、NFC技术:NDEF Uri格式解析
  7. 函数xdes_init
  8. 查找-find -grep
  9. Android系统简介(上):历史渊源
  10. POJ_3280_Cheapest_Palindrome_(动态规划)
  11. AFNetworking 使用方法(2.0)
  12. 利用Python进行数据分析——数据规整化:清理、转换、合并、重塑(七)(1)
  13. 使用slice和concat对数组的深拷贝和浅拷贝
  14. canvas基础(一)
  15. matplotlib-2D绘图库
  16. MVC 模式和模型 2
  17. Django项目关闭debug模式后,静态文件无法加载的解决办法
  18. 读书笔记_Effective_C++_条款三十九:明智而审慎地使用private继承
  19. 关于VS 工具箱灰色,不可用的解决方案
  20. zoj 1037 最短路

热门文章

  1. 霸气的jQ插件
  2. AjaxPro 的基本用法
  3. [算法][C]计算向量的角度
  4. ACM第四站————最小生成树(普里姆算法)
  5. jdbc连接集合
  6. CI框架 QQ接口(第三方登录接口PHP版)
  7. hdu4932 Miaomiao&#39;s Geometry
  8. mysql一些常用命令总结
  9. 滑雪 分类: POJ 2015-07-23 19:48 9人阅读 评论(0) 收藏
  10. Poj(1325),最小点覆盖