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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

URAL1103[Pencils and Circles]  

2011-11-18 17:53:38|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
数学题。
首先可以证明有解当且仅当N不小于3且为奇数。
证明:
若N为偶数或N小于3,显然无解。
若N为不小于3的奇数,那么可以用下面的方法构造一个可行解。
首先选则两点(记为A,B),使得除这两点以外的所有点都在直线AB一侧。
那么若再选一点C,则对A,B,C以外的点(记为D)来说,它在过三角形ABC的外接园内当且仅当角ADB>角ACB。
由此,若把除A,B以外的所有点(记为P[i])排个序,使得对所有可取得的i,角AP[i]B>角AP[i+1]B。
又记排序后的P[i]中的中间那个一个点P[mid]为C。
则对所有i<mid,P[i]在三角形ABC内;对所有i>mid,P[i]在三角形ABC外。
所以三角形ABC即为所求三角形。
然后继续练习Java,这次刚好还用上了大数。
CODE:
import java.io.*;
import
java.util.*;
import
java.math.*;

public class
Ural {
public static
void main(String args[]) throws IOException
{

new
Ural();
}

public
int N;
public
BigInteger x[],y[],ax,ay,bx,by,cx,cy;
public
BigInteger cross(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy)
{

return
bx.subtract(ax).multiply(cy.subtract(ay)).subtract(by.subtract(ay).multiply(cx.subtract(ax)));
}

public
BigInteger dot(BigInteger ax,BigInteger ay,BigInteger bx,BigInteger by,BigInteger cx,BigInteger cy)
{

return
bx.subtract(ax).multiply(cx.subtract(ax)).add(by.subtract(ay).multiply(cy.subtract(ay)));
}

public
boolean less(BigInteger xa,BigInteger ya,BigInteger xb,BigInteger yb)
{

BigInteger
A=BigInteger.valueOf(dot(xa,ya,ax,ay,bx,by).signum()).multiply(dot(xa,ya,ax,ay,bx,by).pow(2).multiply(dot(xb,yb,ax,ay,ax,ay).multiply(dot(xb,yb,bx,by,bx,by))));
BigInteger
B=BigInteger.valueOf(dot(xb,yb,ax,ay,bx,by).signum()).multiply(dot(xb,yb,ax,ay,bx,by).pow(2).multiply(dot(xa,ya,ax,ay,ax,ay).multiply(dot(xa,ya,bx,by,bx,by))));
return
A.compareTo(B)<0;
}

public
void nth_element(int l,int r,int n)
{

int
i=l,j=r;
BigInteger
midx=x[(l+r)/2];
BigInteger
midy=y[(l+r)/2];
while
(i<=j)
{

while
(less(x[i],y[i],midx,midy)) i++;
while
(less(midx,midy,x[j],y[j])) j--;
if
(i<=j)
{

BigInteger
swap;
swap=x[i];
x[i]=x[j];
x[j]=swap;
swap=y[i];
y[i]=y[j];
y[j]=swap;
i++;
j--;
}
}

if
(l<j)
{

if
(n<=j) nth_element(l,j,n);
}

if
(i<r)
{

nth_element(i,r,n-i);
}
}

public
Ural()
{

Scanner
cin=new Scanner(new BufferedInputStream(System.in));
N=cin.nextInt();
if
(N%2!=1)
{

System
.out.println("No solution");
return
;
}

x=new BigInteger[N];
y=new BigInteger[N];
for
(int i=0;i<N;i++)
{

x[i]=cin.nextBigInteger();
y[i]=cin.nextBigInteger();
}

int
ai,bi,ci;
ax=x[0];
ay=y[0];
ai=0;
for
(int i=1;i<N;i++)
if
(x[i].compareTo(ax)>0)
{

ax=x[i];
ay=y[i];
ai=i;
}

N--;
x[ai]=x[N];
y[ai]=y[N];
System
.out.println(ax+" "+ay);
bx=x[0];
by=y[0];
bi=0;
for
(int i=1;i<N;i++)
if
(cross(ax,ay,bx,by,x[i],y[i]).compareTo(BigInteger.valueOf(0))>0)
{

bx=x[i];
by=y[i];
bi=i;
}

N--;
x[bi]=x[N];
y[bi]=y[N];
System
.out.println(bx+" "+by);
nth_element(0,N-1,N/2);
cx=x[N/2];
cy=y[N/2];
System
.out.println(cx+" "+cy);
}
}
  评论这张
 
阅读(510)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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