注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

线段(xd) [nhoi 2016 T5]  

2016-06-05 11:25:12|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

【题目描述】 

         平面上有 N 个不相交的线段,编号 1 到N ,需要模拟下落,即线段不旋转地垂直向下移动到 X 轴下面。如下图:

 线段(xd) [nhoi 2016 T5] - 杨鸿飞 - 一个叫杨鸿飞的人的博客
        现在要你来模拟这个过程,每次向下移动一个线段,N 次后移走全部线段。但有一个要求:移动一
个线段时不能和其他线段相碰。因此选择线段的次序很重要。请输出你制定的次序方案,方案可能有多
个,你只要输出其中的一个。 
【输入格式】 
        第一行包含 1 个整数 N,1≤N ≤5000。 
        下面N 行,每行4 个整数 X1,Y1,X2,Y2,0 ≤  X1,Y1,X2,Y2 ≤ 10000。表示第 1 号到第 N 号线段的 2 个端点。 
【输出格式】 
        一行N 个整数,是1 到N 的一个排列,表示按次序先后下落的线段编号。 
【数据范围】 
40%  1 ≤ N ≤ 10 
60%  1 ≤ N ≤ 300  
===========================================
        首先要知道每条边有几条边在它下面,谁在它的上面(并非上面在上面,即为父亲),让后根据这个拓扑一下,就行了。
        现在就来详细讲讲如何判断:
        第一步:判相交,如图:
        线段(xd) [nhoi 2016 T5] - 杨鸿飞 - 一个叫杨鸿飞的人的博客
        即min(x2,x4)>=max(x1,x3)
        第二步,判上下,相交后谁在上面谁在下面,如图:
        线段(xd) [nhoi 2016 T5] - 杨鸿飞 - 一个叫杨鸿飞的人的博客
                在max(x1,x3)上作一条直线平行于y因为有a/b=d/c,所以d=a*c/b,这样就可以求出两个高度,比谁大即可。 运用了据说是相似三角形的办法。
        没了。
===========================================

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>

using namespace std;

const int ML=5010;

struct Tbian { int x1,x2,y1,y2; } a[ML];
int s[ML];

double Gety(Tbian bb,int xx)
{
int a=abs(bb.y1-bb.y2);
int b=abs(bb.x1-bb.x2);

if (b==0) return min(bb.y1,bb.y2);

int c;

if (bb.y1<bb.y2) c=abs(xx-bb.x1);
else c=abs(xx-bb.x2);

return min(bb.y1,bb.y2)*1.0+a*c*1.00/b;
}

bool PD(int i,int j)
{
Tbian A=a[i],B=a[j];

int lx=max(A.x1,B.x1); int rx=min(A.x2,B.x2);

if (lx>rx) return false;

double pi=Gety(A,lx),pj=Gety(B,lx);

return pi>pj;
}

vector <int> adj[ML];

int op[ML];

int main()
{
ios::sync_with_stdio(false);

freopen("xd.in","r",stdin);
freopen("xd.out","w",stdout);

int n; cin>>n;

for (int i=0; i<n; i++)
{
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2; //读入
if (a[i].x1>a[i].x2) //使x1小于x2,为了避免后面多次运用min,max。
{ swap(a[i].x1,a[i].x2); swap(a[i].y1,a[i].y2); }
}

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (i!=j && PD(i,j))
s[i]++,adj[j].push_back(i); //入度++,j连去i
/*==================拓扑(bfs实现)=================*/
int Head=0,Tail=0;

for (int i=0; i<n; i++) if (s[i]==0) op[Tail++]=i; //找入度为0的入队

for ( ; Head<Tail; Head++)
{
int pp=op[Head];

cout<<pp+1<<" ";

s[pp]--;

for (int j=0; j<adj[pp].size(); j++)
{
int np=adj[pp][j];
s[np]--;
if (s[np]==0) op[Tail++]=np;
}
}

return 0;
}


  
  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018