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

qus的博客

 
 
 

日志

 
 

poj2165  

2009-08-10 08:38:52|  分类: POJ解题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一道wa得泪流满面的题目啊。题目要求的6位精度的确令人相当郁闷。

做法,X和Y可疑分开处理,Y可以由极角序排列,很容易求。至于X,和lrj那题管道差不多,就是枚举任意两点,判相交。

关于精度,我以前延长线段到直线求交点,是直接延长到1e10,含义是无穷远,但是在这题上栽了无数次,最后,要把交点,设在范围的附近,就终于过了。教训了~~以后懂了。

这题数据量还是挺小的。

 

5603774 gtzygtzy 2165 Accepted 216K 16MS C++ 3967B 2009-08-08 21:21:27

 

#include<iostream>

#include<iomanip>

#include<math.h>

#define MAXL 110

#define dps 1e-9

using namespace std;

struct node

{

 double x1,x2,y1,y2,z;

}seg[MAXL];

struct node2

{

 double jiao;

 int re;

}up[MAXL],down[MAXL];

struct point

{

 double x,y;

};

struct point3

{

 double x,y,z;

}result[MAXL];

double result_x;

int n;

int dblcmp(double d)//鐟欙絽鍠呯划鎯у閻ㄥ嫬鍨介弬顓炵毈娴?

{

 if(fabs(d)<dps) return 0;

 return (d>0)?1:-1;

}

double mymin(double a,double b)

{return a<b?a:b;}

double mymax(double a,double b)

{return a>b?a:b;}

double det(double x1,double y1,double x2,double y2)//濮瑰倷琚辨稉顏勬倻闁插繐寮剁粔?

{

 return x1*y2-x2*y1;

}

double cross(point a,point b,point c)//濮?娑擃亞鍋i惃鍕级缁?

{

 return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);

}

int xycmp(double p,double mini,double maxi)

{

 return dblcmp(p-mini)*dblcmp(p-maxi);

}

int betweencmp(point a,point b,point c) //瀹歌尙绮¢惌銉╀壕a閸︹暈c閻╁鍤庢稉?,鏉╂柨娲栭崐? 娑撳秴婀柌宀勬桨閿? c閸︺劎顏悙绛ч幋鏍偓鍗?閿涘矉绱? c閸︺劎顏悙绛?b娑斿妫?

{

 if(fabs(b.x-c.x)>fabs(b.y-c.y)) return xycmp(a.x,mymin(b.x,c.x),mymax(b.x,c.x));

 else return xycmp(a.y,mymin(b.y,c.y),mymax(b.y,c.y));

}

int segcross(point a,point b,point c,point d,point &p)//p閻€劋绨鏇犳暏鏉╂柨娲栭弫?

{

 double s1,s2,s3,s4;

 int d1,d2,d3,d4;

 d1=dblcmp(s1=cross(a,b,c));

 d2=dblcmp(s2=cross(a,b,d));

 d3=dblcmp(s3=cross(c,d,a));

 d4=dblcmp(s4=cross(c,d,b));

 //閸掋倖鏌囩憴鍕瘱閻╅晲姘?

 if((d1^d2)==-2&&(d3^d4)==-2)

 {

  p.x=(c.x*s2-d.x*s1)/(s2-s1);

  p.y=(c.y*s2-d.y*s1)/(s2-s1);

  return 1;

 }

 //閸掋倖鏌囬棃鐐额潐閼煎啰娴夋禍?

 if(d1==0&&betweencmp(c,a,b)<=0) {p=c;return 2;}

 if(d2==0&&betweencmp(d,a,b)<=0) {p=d;return 2;}

 if(d3==0&&betweencmp(a,c,d)<=0) {p=a;return 2;}

 if(d4==0&&betweencmp(b,c,d)<=0) {p=d;return 2;}

 return 0;

}

int com_up(const void *p1,const void *p2)

{

 node2 q1=*(node2*)p1;

 node2 q2=*(node2*)p2;

 return dblcmp(q1.jiao-q2.jiao);

}

int com_down(const void *p1,const void *p2)

{

 node2 q1=*(node2*)p1;

 node2 q2=*(node2*)p2;

 return dblcmp(q2.jiao-q1.jiao);

}

bool check(point a,point b)

{

 double dx=a.x-b.x;

 double dy=a.y-b.y;

 point aa;

 result_x=dx*(-a.y)/dy+a.x;

 aa=a;

 a.y=-10.0;b.y=1100.0;

 a.x=dx*(a.y-aa.y)/dy+aa.x;

 b.x=dx*(b.y-aa.y)/dy+aa.x;

 point c,d,return_point;

 int i;

 for(i=0;i<n;i++)

 {

  c.x=seg[i].x1;c.y=seg[i].z;

  d.x=seg[i].x2;d.y=seg[i].z;

  if(segcross(a,b,c,d,return_point)==0) return false;

  result[i].x=return_point.x;

 }

 return true;

}

int main()

{

 //freopen("in.txt","r",stdin);

 int i,j;

 //point ,c,d,return_point;

 point a,b;

 //double dx,dy,temp;

 double temp;

 bool work;

 scanf("%d",&n);

 for(i=0;i<n;i++)

 {

  scanf("%lf%lf%lf%lf%lf",&seg[i].x1,&seg[i].y1,&seg[i].x2,&seg[i].y2,&seg[i].z);

 // seg[i].x1*=1000.0;seg[i].y1*=1000.0;

 // seg[i].x2*=1000.0;seg[i].y2*=1000.0;

 // seg[i].z*=1000.0;

  result[i].z=seg[i].z;

 }

 //check y

 for(i=0;i<n;i++)

 {

  up[i].re=i;

  up[i].jiao=(seg[i].y2/seg[i].z);

  down[i].re=i;

  down[i].jiao=(seg[i].y1/seg[i].z);

 }

 qsort(up,n,sizeof(up[0]),com_up);

 qsort(down,n,sizeof(down[0]),com_down);

 if(dblcmp(up[0].jiao-down[0].jiao)<0)

 {

  printf("UNSOLVABLE\n");

  return 0;

 }

 temp=up[0].jiao;

 for(i=0;i<n;i++)

 {

  result[i].y=temp*seg[i].z;

 }

 //check x;

 work=false;

 for(i=0;i<n;i++)

 {

  a.x=seg[i].x1;a.y=seg[i].z;

  for(j=i+1;j<n;j++)

  {

   b.x=seg[j].x1;b.y=seg[j].z;

   if(check(a,b)) {work=true;break;}

   b.x=seg[j].x2;b.y=seg[j].z;

   if(check(a,b)) {work=true;break;}

  }

  if(work) break;

  a.x=seg[i].x2;a.y=seg[i].z;

  for(j=i+1;j<n;j++)

  {

   b.x=seg[j].x1;b.y=seg[j].z;

   if(check(a,b)) {work=true;break;}

   b.x=seg[j].x2;b.y=seg[j].z;

   if(check(a,b)) {work=true;break;}

  }

  if(work) break;

 }

 if(!work)

 {

  printf("UNSOLVABLE\n");

  return 0;

 }

 printf("SOLUTION\n");

// printf("%.6lf\n",result_x);

 cout<<setiosflags(ios::fixed)<<setprecision(6)<<result_x<<endl;

 for(i=0;i<n;i++)

 {

  printf("%.6lf %.6lf %.6lf\n",result[i].x,result[i].y,result[i].z);

 }

 return 0;

}

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

历史上的今天

评论

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

页脚

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