//和2318差不多，只是輸入的board是無序的，輸出是玩具數為t(>0)的箱子數(>0)
#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXN 5000+1
#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
struct point
{int x,y;};
struct line{point a,b;};
int ans[MAXN];
line board[MAXN];
double xmult(point p0,point p1,point p2){//叉積，囧
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int cmp(const void *a,const void *b)
{
line *aa=(line*)a,*bb=(line*)b;
if(aa->a.x == bb->a.x)
return aa->b.x - bb->b.y;
else return aa->a.x - bb->a.x;
}
int main()
{
int n,m,x1,y1,x2,y2,u1,u2,i;
point toys;
while(scanf("%d",&n)!=EOF && n )
{
memset(ans,0,sizeof(ans));
scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
{
scanf("%d%d",&u1,&u2);
board[i].a.x=u1;
board[i].a.y=y1;
board[i].b.x=u2;
board[i].b.y=y2;
}
qsort(board,n,sizeof(board[0]),cmp);
board[n].a.x=x2;
board[n].a.y=y1;
board[n].b.x=x2;
board[n].b.y=y2;
for(i=0;i<m;i++)
{
scanf("%d%d",&(toys.x),&(toys.y));
int low=0,hig=n,mid;
while(low+1<hig)
{
mid=(low+hig)>>1;
double res=xmult(board[mid].a,board[mid].b,toys);
if(res>0) low=mid;
else hig=mid;
}
if(xmult(board[low].a,board[low].b,toys)<0) ans[low]++;
else ans[low+1]++;
}
printf("Box\n");
int t=1,c;
for(t=1;t<=m;t++)
{
for(i=0,c=0;i<=n;i++)
{
if(ans[i]==t)
{
c++;
ans[i]=0;
}
}
if(c>0)
printf("%d: %d\n",t,c);
m=m-c*t;
}
}
return 0;
}posted @
2009-10-04 13:12 wyiu 閱讀(203) |
評論 (0) |
編輯 收藏//今天開始按著這個來做題訓練計算幾何了
計算幾何題的特點與做題要領：
1.大部分不會很難，少部分題目思路很巧妙
2.做計算幾何題目，模板很重要，模板必須高度可靠。
3.要注意代碼的組織，因為計算幾何的題目很容易上兩百行代碼，里面大部分是模板。如果代碼一片混亂，那么會嚴重影響做題正確率。
4.注意精度控制。
5.能用整數的地方盡量用整數，要想到擴大數據的方法（擴大一倍，或擴大sqrt2）。因為整數不用考慮浮點誤差，而且運算比浮點快。
一。點，線，面，形基本關系，點積叉積的理解
POJ 2318 TOYS（推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
POJ 2398 Toy Storage（推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2398
一個矩形，有被若干直線分成N個格子，給出一個點的坐標，問你該點位于哪個點中。
知識點：其實就是點在凸四邊形內的判斷，若利用叉積的性質，可以二分求解。
POJ 3304 Segments
http://acm.pku.edu.cn/JudgeOnline/problem?id=3304
知識點：線段與直線相交，注意枚舉時重合點的處理
POJ 1269 Intersecting Lines
http://acm.pku.edu.cn/JudgeOnline/problem?id=1269
知識點：直線相交判斷，求相交交點
POJ 1556 The Doors （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1556
知識點：簡單圖論＋簡單計算幾何，先求線段相交，然后再用Dij求最短路。
POJ 2653 Pick-up sticks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
知識點：還是線段相交判斷
POJ 1066 Treasure Hunt
http://acm.pku.edu.cn/JudgeOnline/problem?id=1066
知識點：線段相交判斷，不過必須先理解“走最少的門”是怎么一回事。
POJ 1410 Intersection
http://acm.pku.edu.cn/JudgeOnline/problem?id=1410
知識點：線段與矩形相交。正確理解題意中相交的定義。
詳見：http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html
POJ 1696 Space Ant （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1696
德黑蘭賽區的好題目。需要理解點積叉積的性質
POJ 3347 Kadj Squares
http://acm.pku.edu.cn/JudgeOnline/problem?id=3347
本人的方法極度猥瑣。復雜的線段相交問題。這個題目是計算幾何的擴大數據運算的典型應用，擴大根號2倍之后就避免了小數。
POJ 2826 An Easy Problem?! （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2826
問：兩條直線組成一個圖形，能容納多少雨水。很不簡單的Easy Problem，要考慮所有情況。你不看discuss看看能否AC。（本人基本不能）提示一下，水是從天空垂直落下的。
POJ 1039 Pipe
http://acm.pku.edu.cn/JudgeOnline/problem?id=1039
又是線段與直線相交的判斷，再加上枚舉的思想即可。
POJ 3449 Geometric Shapes
http://acm.pku.edu.cn/JudgeOnline/problem?id=3449
判斷幾何體是否相交，不過輸入輸出很惡心。
此外，還有一個知識點，就是給出一個正方形（邊不與軸平行）的兩個對角線上的頂點，需要你求出另外兩個點。必須掌握其方法。
POJ 1584 A Round Peg in a Ground Hole
http://acm.pku.edu.cn/JudgeOnline/problem?id=1584
知識點：點到直線距離，圓與多邊形相交，多邊形是否為凸
POJ 2074 Line of Sight （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2074
與視線問題的解法，關鍵是求過兩點的直線方程，以及直線與線段的交點。數據有一個trick，要小心。
二。凸包問題
POJ 1113 Wall
http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
知識點：赤裸裸的凸包問題，凸包周長加上圓周。
POJ 2007 Scrambled Polygon
http://acm.pku.edu.cn/JudgeOnline/problem?id=2007
知識點：凸包，按極角序輸出方案
POJ 1873 The Fortified Forest （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1873
World Final的水題，先求凸包，然后再搜索。由于規模不大，可以使用位運算枚舉。
詳見：http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html
POJ 1228 Grandpa's Estate （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
求凸包頂點數目，很多人求凸包的模板是會多出點的，雖然求面積時能得到正確答案，但是在這個題目就會出問題。此外，還要正確理解凸包的性質。
POJ 3348 Cows
http://acm.pku.edu.cn/JudgeOnline/problem?id=3348
凸包面積計算
三。面積問題，公式問題
POJ 1654 Area
http://acm.pku.edu.cn/JudgeOnline/problem?id=1654
知識點：利用有向面積（叉積）計算多邊形面積
POJ 1265 Area
http://acm.pku.edu.cn/JudgeOnline/problem?id=1265
POJ 2954 Triangle
http://acm.pku.edu.cn/JudgeOnline/problem?id=2954
Pick公式的應用，多邊形與整點的關系。（存在一個GCD的關系）
四。半平面交
半平面交的主要應用是判斷多邊形是否存在核，還可以解決一些與線性方程組可行區域相關的問題（就是高中時的那些）。
POJ 3335 Rotating Scoreboard
http://acm.pku.edu.cn/JudgeOnline/problem?id=3335
POJ 3130 How I Mathematician Wonder What You Are!
http://acm.pku.edu.cn/JudgeOnline/problem?id=3130
POJ 1474 Video Surveillance
http://acm.pku.edu.cn/JudgeOnline/problem?id=1474
知識點：半平面交求多邊形的核，存在性判斷
POJ 1279 Art Gallery
http://acm.pku.edu.cn/JudgeOnline/problem?id=1279
半平面交求多邊形的核，求核的面積
POJ 3525 Most Distant Point from the Sea （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3525
給出一個多邊形，求里面的一個點，其距離離多邊形的邊界最遠，也就是多邊形中最大半徑圓。
可以使用半平面交+二分法解。二分這個距離，邊向內逼近，直到達到精度。
POJ 3384 Feng Shui （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3384
半平面交實際應用，用兩個圓覆蓋一個多邊形，問最多能覆蓋多邊形的面積。
解法：用半平面交將多邊形的每條邊一起向“內”推進R，得到新的多邊形，然后求多邊形的最遠兩點。
POJ 1755 Triathlon （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1755
半平面交判斷不等式是否有解。注意不等式在轉化時正負號的選擇，這直接影響到半平面交的方向。
POJ 2540 Hotter Colder
http://acm.pku.edu.cn/JudgeOnline/problem?id=2540
半平面交求線性規劃可行區域的面積。
POJ 2451 Uyuw's Concert
http://acm.pku.edu.cn/JudgeOnline/problem?id=2451
Zzy專為他那篇nlogn算法解決半平面交問題的論文而出的題目。
五。計算幾何背景，實際上解題的關鍵是其他問題（數據結構、組合數學，或者是枚舉思想）
若干道經典的離散化＋掃描線的題目，ACM選手必做題目
POJ 1151 Atlantis （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
POJ 1389 Area of Simple Polygons
http://acm.pku.edu.cn/JudgeOnline/problem?id=1389
矩形離散化，線段樹處理，矩形面積求交
POJ 1177 Picture （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
矩形離散化，線段樹處理，矩形交的周長，這個題目的數據比較強。線段樹必須高效。
POJ 3565 Ants （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3565
計算幾何中的調整思想，有點像排序。要用到線段相交的判斷。
詳見：http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html
POJ 3695 Rectangles
http://acm.pku.edu.cn/JudgeOnline/problem?id=3695
又是矩形交的面積，但是由于是多次查詢，而且矩形不多，使用組合數學中的容斥原理解決之最適合。線段樹是通法，但是除了線段樹，還有其他可行的方法。
POJ 2002 Squares
http://acm.pku.edu.cn/JudgeOnline/problem?id=2002
枚舉思想，求平面上若干個點最多能組成多少個正方形，點的Hash
POJ 1434 Fill the Cisterns!（推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1434
一開始發昏了，準備弄個線段樹。其實只是個簡單的二分。
六。隨機算法
POJ 2420 A Star not a Tree?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2420
多邊形的費馬點。所謂費馬點，就是多邊形中一個點P，該點到其他點的距離之和最短。四邊形以上的多邊形沒有公式求費馬點，因此可以使用隨機化變步長貪心法。
詳見：http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html
七。解析幾何
這種題目本人不擅長，所以做得不多，模板很重要。當然，熟練運用叉積、點積的性質還是很有用的。
POJ 1375 Intervals
http://acm.pku.edu.cn/JudgeOnline/problem?id=1375
知識點：過圓外一點求與圓的切線
POJ 1329 Circle Through Three Points
http://acm.pku.edu.cn/JudgeOnline/problem?id=1329
求三角形外接圓
POJ 2354 Titanic
http://acm.pku.edu.cn/JudgeOnline/problem?id=2354
求球面上兩個點的距離，而且給的是地理經緯坐標。
POJ 1106 Transmitters
http://acm.pku.edu.cn/JudgeOnline/problem?id=1106
角度排序，知道斜率求角度，使用atan函數。
POJ 1673 EXOCENTER OF A TRIANGLE
http://acm.pku.edu.cn/JudgeOnline/problem?id=1673
可以轉化為三角形的垂心問題。
八。旋轉卡殼
POJ 2187 Beauty Contest
http://acm.pku.edu.cn/JudgeOnline/problem?id=2187
凸包求最遠點對。可以暴力枚舉，也可以使用旋轉卡殼。
POJ 3608 Bridge Across Islands（難）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3608
兩個凸包的最近距離。本人的卡殼始終WA。郁悶。
九。其他問題
POJ 1981 Circle and Points
http://acm.pku.edu.cn/JudgeOnline/problem?id=1981
求單位圓最多能覆蓋平面上多少個點
posted @
2009-10-04 12:18 wyiu 閱讀(130) |
評論 (0) |
編輯 收藏
//計算幾何第一題
//學習了叉積和利用叉積判斷左右位置關系
//叉積+二分
//延續了這兩天比賽的PE黑手
#include<iostream>
using namespace std;
#define MAXN 5000+1
#define eps 1e-8
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
struct point{int x,y;};
struct line{point a,b;};
int ans[MAXN];
point toys[MAXN];
line board[MAXN];
double xmult(point p0,point p1,point p2){//叉積，囧
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int main()
{
int n,m,x1,y1,x2,y2,u1,u2,i;
bool flag=false;
while(scanf("%d",&n)!=EOF && n )
{
if(flag) printf("\n");
memset(ans,0,sizeof(ans));
scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
for(i=0;i<n;i++)
{
scanf("%d%d",&u1,&u2);
board[i].a.x=u1;
board[i].a.y=y1;
board[i].b.x=u2;
board[i].b.y=y2;
}
board[n].a.x=x2;
board[n].a.y=y1;
board[n].b.x=x2;
board[n].b.y=y2;
for(i=0;i<m;i++)
{
scanf("%d%d",&(toys[i].x),&(toys[i].y));
int low=0,hig=n,mid;
while(low+1<hig)
{
mid=(low+hig)>>1;
double res=xmult(board[mid].a,board[mid].b,toys[i]);
//if(res>0)
if(res>0) low=mid;
else hig=mid;
}
if(xmult(board[low].a,board[low].b,toys[i])<0) ans[low]++;
else ans[low+1]++;
}
for(i=0;i<=n;i++)
{
printf("%d: %d\n",i,ans[i]);
}
flag=true;
}
return 0;
}
posted @
2009-10-04 12:14 wyiu 閱讀(153) |
評論 (0) |
編輯 收藏1.判斷左右－叉積
設向量a和b，a×b表示a和b的叉積
a×b=xayb-xbya
三維：a×b=(yazb-ybza)i+(xazb-xbza)j+(xayb-xbya)k，i,j,k是x,y,z軸上的單位向量。
>0，ab成右手系
=0，ab重疊或平行
<0，ab成左手系
此外，叉積還可以用來計算兩向量所圍成的三角形，S=ab/2
2.判斷相交
設線段AB和CD
(AB×AC)(AB×AD)<0且(CD×CA)(CD×CB)<0
3.向量夾角－點積
設向量a和b，a·b表示a和b的叉積
a·b＝xaxb+yayb
三維：a·b＝xaxb+yayb+zazb
α=arccos((a·b)/|a||b|)
>0，α是銳角
=0，α是直角，ab垂
<0，α是鈍角
4.點P到直線AB的距離=PA×PB/|AB|
點P到平面ABC的距離=PA·(AB×AC)/|AB×AC|（注意是三維的叉積和點積）
5．判斷線段ab和cd相交的另一種方法
xa+(xb-xa)i=xc+(xd-xc)j
ya+(yb-ya)i=yc+(yd-yc)j
解這個方程組，有：
如果i,j∈(0,1)，那么ab和cd相交，且交點坐標是
(xa+(xb-xa)i, ya+(yb-ya)i)
這個方法可以推廣到3維情況，只要列個三元方程就行了。
posted @
2009-10-04 11:31 wyiu 閱讀(225) |
評論 (0) |
編輯 收藏
int main( int argc , char *argv[] , char *envp[] )
main()函數一般用int或者void形的。我比較喜歡用int型定義main。因為在結束的時候可以返回給操作系統一個值以表示執行情況。
int argc
這個東東用來表示你在命令行下輸入命令的時候，一共有多少個參數。比方說你的程序編譯后，可執行文件是test.exe
D:\tc2>test
這個時候，argc的值是1
但是
D:\tc2>test.exe myarg1 myarg2
的話，argc的值是3。也就是 命令名 加上兩個參數，一共三個參數
char *argv[]
這個東東用來取得你所輸入的參數
D:\tc2>test
這個時候，argc的值是1，argv[0]的值是 "test"
D:\tc2>test myarg1 myarg2
這個時候，argc的值是3，argc[0]的值是"test"，argc[1]的值是"myarg1"，argc[2]的值是"myarg2"。
這個東東一般用來為程序提供非常重要的信息，如：數據文件名，等等。
如：copy a.c b.txt
這個時候，a.c和b.txt就是所謂的“非常重要的信息”。不指定這兩個文件，你沒法進行拷貝。
當你的程序用到argc和argv這兩個參數的時候，可以簡單地通過判斷argc的值，來看看程序的參數是否符合要求
char *envp[]
這個東東相對來說用得比較少。它是用來取得系統的環境變量的。
如：在DOS下，有一個PATH變量。當你在DOS提示符下輸入一個命令（當然，這個命令不是dir一類的內部命令）的時候，DOS會首先在當前目錄下找這個命令的執行文件。如果找不到，則到PATH定義的路徑下去找，找到則執行，找不到返回Bad command or file name
在DOS命令提示符下鍵入set可查看系統的環境變量
同樣，在UNIX或者LINUX下，也有系統環境變量，而且用得比DOS要多。如常用的$PATH,$USER,$HOME等等。
envp保存所有的環境變量。其格式為（UNIX下）
PATH=/usr/bin;/local/bin;
HOME=/home/shuui
即：
環境變量名=值
DOS下大概也一樣。
環境變量一般用來為程序提供附加信息。如，你做了一個顯示文本的內容的程序。你想控制其一行中顯示的字符的個數。你可以自己定義一個環境變量（UNIX下）
%setenv NUMBER = 10
%echo $NUMBER
10
然后你可以在程序中讀入這個環境變量。然后根據其值決定一行輸出多少個字符。這樣，如果你不修改環境變量的話，你每次執行這個程序，一行中顯示的字符數都是不一樣的
下面是一個例子程序
/* argtest.c */
#include<stdio.h>
int main( int argc , char *argv[] , char *envp[] )
{
int i;
printf( "You have inputed total %d argments\n" , argc );
for( i=0 ; i<argc ; i++)
{
printf( "arg%d : %s\n" , i , argv[i] );
}
printf( "The follow is envp :\n" );
for( i=0 ; *envp[i]!='\0' ; i++ )
{
printf( "%s\n" , envp[i] );
}
return 0;
}
D:\>argtest this is a test programe of main()'s argments
You have inputed total 9 argments
arg0 : D:\TC\NONAME.EXE
arg1 : this
arg2 : is
arg3 : a
arg4 : test
arg5 : programe
arg6 : of
arg7 : main()'s
arg8 : argments
The follow is envp :
TMP=C:\WINDOWS\TEMP
TEMP=C:\WINDOWS\TEMP
PROMPT=$p$g
winbootdir=C:\WINDOWS
PATH=C:\WINDOWS;C:\WINDOWS\COMMAND
COMSPEC=C:\WINDOWS\COMMAND.COM
SBPCI=C:\SBPCI
windir=C:\WINDOWS
BLASTER=A220 I7 D1 H7 P330 T6
CMDLINE=noname this is a test programe of main()'s argments
posted @
2009-10-03 21:44 wyiu 閱讀(209) |
評論 (0) |
編輯 收藏//第33屆ACM-ICPC亞洲預選賽成都賽區解題報告
Problem J
Counting Square
//o(n^2)處理，o(n^3)枚舉
#include<iostream>
using namespace std;
int mat[301][301];
int sum[301][301];
int main()
{
int t;
int r,c;
int res=0;
int i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&r,&c);
memset(sum,0,sizeof(sum));
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
scanf("%d",&mat[i][j]);
if(mat[i][j]==0) mat[i][j]=-1;
sum[i][j]=mat[i][j]-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1];
}
res=0;
for(i=1;i<r;i++)
for(j=1;j<c;j++)
{
if(mat[i][j]==-1 || mat[i][j+1]==-1 || mat[i+1][j]==-1 ) continue;
int all=0,bo=0,in=0;
for(k=1;i+k<=r && j+k<=c;k++)
{
all=sum[i+k][j+k]-sum[i+k][j-1]-sum[i-1][j+k]+sum[i-1][j-1];
in=sum[i+k-1][j+k-1]-sum[i+k-1][j]-sum[i][j+k-1]+sum[i][j];
bo=all-in;
if(bo<4*k) continue;
else if(in<=1 && in>=-1) res++;
}
}
printf("%d\n",res);
}
return 0;
}
posted @
2009-09-09 23:49 wyiu 閱讀(229) |
評論 (0) |
編輯 收藏
傳說可以用kmp的精髓next[]來做，但是怎么都領悟不了，所以就憑感覺直接模擬了
因為s=a^n
取前綴，分別從長度1到strlen，然后與后面剩下的比較，如果ok就說明這個長度是a的最短的長度，然后sterlen(s)/strlen(a)
#include<iostream>
using namespace std;
#define M 1000000
char t[M+1],p[M+1];
int lent,lenp;
bool kmp(char *t,char *p)
{
int i,j;
for(i=lenp,j=0;i<lent;i++)
{
if(t[i]!=p[j]) return false;
if(t[i]==p[j]) j++;
if(j==lenp) j=0;
}
return true;
}
int main()
{
int i;
while(scanf(" %s",&t)!=EOF && t[0]!='.')
{
lent=strlen(t);
for(i=0;i<lent;i++)
{
p[i]=t[i];
p[i+1]='\0';
lenp=i+1;
if(lent%lenp==0 && kmp(t,p))
{
printf("%d\n",lent/lenp);
break;
}
}
}
return 0;
}
posted @
2009-08-03 14:25 wyiu 閱讀(286) |
評論 (0) |
編輯 收藏#include<iostream>
using namespace std;
#define M 1000
//int kmp(char *t,char *p,int pos)
int kmp(char *t,char *p)
{
//p模式串，t主串
//預處理
int next[M];
//memset(next,0,sizeof(next));
int i,j,
lent=strlen(t),
lenp=strlen(p);
next[0]=-1;
i=0;j=-1;
while(i<lenp-1)
{
if(j==-1 || p[i]==p[j])
{
++i;++j;
if(p[i]!=p[j]) next[i]=j;
else next[i]=next[j];
//next[i]=j;
}
else j=next[j];
}
//匹配
i=0;j=0;
while(i<lent && j<lenp)
{
if(j==-1 || t[i]==p[j]) {++i;++j;}
else j=next[j];
}
if(j==lenp) return i-lenp;
else return -1;
}
int main()
{
char t[100],p[100];
while(cin>>t>>p)
cout<<kmp(t,p)<<endl;
return 0;
}
//
posted @
2009-07-30 17:22 wyiu 閱讀(164) |
評論 (0) |
編輯 收藏
//
#include<iostream>
#include<cmath>
using namespace std;
struct BALL
{
double x,y,z,r;
};
struct Edge
{
int x,y;
double w;
};
BALL ball[200];
Edge edge[10000];
int parent[200];
int n;
int find(int c)
{
if(parent[c]<0) return c;
else return find(parent[c]);
}
bool uni(int x,int y)
{
int a,b,t;
a=find(x);
b=find(y);
if(a!=b)
{
t=parent[a]+parent[b];
if(parent[a]<parent[b])
{
parent[b]=a;
parent[a]=t;
}
else
{
parent[a]=b;
parent[b]=t;
}
return true;
}
return false;
}
double Kruskal(int en)
{
int i;
double mst=0;
memset(parent,-1,sizeof(parent));
for(i=0;i<en;i++)
if(uni(edge[i].x,edge[i].y))
mst+=edge[i].w;
return mst;
}
int cmp(const void *a, const void *b)
{
double ta=(*(Edge*)a).w,tb=(*(Edge*)b).w;
if(ta<tb) return -1;
else if(ta==tb) return 0;
else return 1;
}
int main()
{
int i,j,k;
double dx,dy,dz,ts;
while(scanf("%d",&n)!=EOF && n)
{
for(i=0;i<n;i++)
scanf("%lf%lf%lf%lf",&(ball[i].x),&(ball[i].y),&(ball[i].z),&(ball[i].r));
for(i=0,k=0;i<n;i++)
for(j=i+1;j<n;j++)
{
edge[k].x=i;
edge[k].y=j;
dx=ball[i].x-ball[j].x;
dy=ball[i].y-ball[j].y;
dz=ball[i].z-ball[j].z;
ts=pow(dx*dx+dy*dy+dz*dz,0.5);
if(ts>ball[i].r+ball[j].r)
edge[k++].w=ts-ball[i].r-ball[j].r;
else edge[k++].w=0;
}
qsort(edge,k,sizeof(edge[0]),cmp);
printf("%.3lf\n",Kruskal(k));
}
}
posted @
2009-07-29 10:05 wyiu 閱讀(160) |
評論 (0) |
編輯 收藏#include<iostream>
#include<cmath>
using namespace std;
#define M 40000
__int64 sum[M+1];
__int64 len[M+1];
void init()
{
int i;
len[0]=0;
sum[0]=0;
for(i=1;i<=M;i++)
{
len[i]=len[i-1]+(int)log10(double(i))+1;
sum[i]=sum[i-1]+len[i];
}
}
int search(__int64 n)
{
__int64 k,w,li,i,j;
k=1;
while(sum[k]<n) k++;//di k zu
w=n-sum[k-1];//
i=1;
while(w-int(log10(double(i))+1)>0)
{
w-=int(log10(double(i))+1);
i++;
}
li=(int)log10((double)i)+1;
for(j=1;j<=li-w;j++)
i/=10;
return i%10;
}
int main()
{
init();
int t;
__int64 n;
scanf("%d",&t);
for(;t--;)
{
scanf("%I64d",&n);
printf("%d\n",search(n));
}
return 0;
}
posted @
2009-07-28 09:43 wyiu 閱讀(422) |
評論 (2) |
編輯 收藏