YAIMH1993的笔记 如果奇迹木有出现，就去创造一个

posted @ 2012-10-24 01:04 YouAreInMyHeart 阅读(100) | 评论 (0)编辑 收藏

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct point { double x,y; };
bool mult(point sp,point ep,point op){
return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}

bool operator < (const point &l,const point &r){
return l.y<r.y || (l.y==r.y && l.x < r.x);
}

int graham(point pnt[],int n,point res[]){ //pnt是图中的所有的点，res是通过判断后在凸边行边上的点，而且这些点都是按逆时针存储的，n是所有点的个数
int i,len,k = 0,top = 1;
sort(pnt,pnt+n);
if(n == 0) return 0; res[0]=pnt[0];
if(n == 1) return 1; res[1]=pnt[1];
if(n == 2) return 2; res[2]=pnt[2];
for(i=2;i<n;i++) {
while(top && mult(pnt[i],res[top],res[top-1]))
top--;
res[++top] = pnt[i];
}
len = top; res[++top] = pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len && mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
}

point res[50001],pnt[50001];

int main() {
int n;
while(~scanf("%d",&n) && n) {
for(int i=0;i<n;i++) scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
if(graham(pnt,n,res) == n) puts("convex");
else puts("concave");
}
return 0;
}

posted @ 2012-10-24 00:57 YouAreInMyHeart 阅读(63) | 评论 (0)编辑 收藏
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[7];
int dp[121111];
int v,k;
void ZeroOnePack(int cost,int weight) {
for(int i=v;i>=cost;i--)
dp[i] = max(dp[i] , dp[i-cost] + weight);
}
void CompletePack(int cost,int weight) {
for(int i=cost;i<=v;i++)
dp[i] = max(dp[i] , dp[i-cost] + weight);
}
void MultiplePack(int cost,int weight,int amount) {
if(cost * amount >= v) CompletePack(cost,weight);
else {
for(int k=1;k<amount;) {
ZeroOnePack(k*cost,k*weight);
amount -= k;
k <<= 1;
}
ZeroOnePack(amount*cost,amount*weight);
}
}
int main() {
int cas = 1;
while(1) {
int tot = 0;
for(int i=1;i<=6;i++) {
scanf("%d",&a[i]);
tot += a[i] * i;
}
if(tot == 0) break;
printf("Collection #%d:\n",cas++);
if(tot % 2) puts("Can't be divided.");
else {
v = tot / 2;
memset(dp,0,sizeof(dp));
for(int i=1;i<=6;i++) {
MultiplePack(i,i,a[i]);
}
if(dp[v] == v) puts("Can be divided.");
else puts("Can't be divided.");
}
puts("");
}
return 0;
}
posted @ 2012-10-23 21:38 YouAreInMyHeart 阅读(75) | 评论 (0)编辑 收藏
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int t;
double n,a,b;
int main() {
scanf("%d",&t);
while(t--) {
scanf("%lf",&n);
a = n * log10(n);
b = pow(10 , a - floor(a));
printf("%d\n",(int)b);
}
return 0;
}
posted @ 2012-10-22 12:06 YouAreInMyHeart 阅读(68) | 评论 (0)编辑 收藏

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace
std;
int
a[5843] = {0,1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,。。。。。。,1990656000,1991485440,1992903750,1993359375,2000000000};
int
main() {
int
n;
while
(~scanf("%d",&n) && n) {
printf("The %d",n);
if
(n % 100 >= 11 && n % 100 <= 13) printf("th "); else if(n % 10 == 1) printf("st ");
else if
(n % 10 == 2) printf("nd ");
else if
(n % 10 == 3) printf("rd ");
else
printf("th ");
printf("humble number is %d.\n",a[n]);
}

return
0;
}

posted @ 2012-10-22 11:24 YouAreInMyHeart 阅读(55) | 评论 (0)编辑 收藏
http://walcl.cn/post/85.html
posted @ 2012-10-22 09:16 YouAreInMyHeart 阅读(75) | 评论 (0)编辑 收藏

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[1111] , b[1111];
int s1 , e1 , s2 ,e2;
int n;
bool cmp(int a,int b) {
return a > b;
}
void solve() {
s1 = s2 = 0;
e1 = e2 = n - 1;
int ans = 0;
for(;s1 <= e1;) {
if(a[e1] > b[e2]) ans ++,e1--,e2--;
else if(a[s1] > b[s2]) ans ++,s1++,s2++;
else {
if(a[e1] != b[s2]) ans --;
e1 -- , s2 ++;
}
}
printf("%d\n",ans*200);
}
int main() {
while(~scanf("%d",&n) && n) {
for(int i=0;i<n;i++) scanf("%d",a+i);
for(int i=0;i<n;i++) scanf("%d",b+i);
sort(a,a+n,cmp);
sort(b,b+n,cmp);
solve();
}
return 0;
}
posted @ 2012-10-22 08:57 YouAreInMyHeart 阅读(52) | 评论 (0)编辑 收藏

#include <cstdio>
#include <cstring>
using namespace std;
bool vis[33];
char map[5][5];
int mapl[5][5],mapr[5][5];
int n , m;
bool find(int u) {
for(int v=1;v<=m;v++)
if(g[u][v] && !vis[v]) {
vis[v] = 1;
return true;
}
}
return false;
}
int hungry() {
int ret = 0;
for(int u=1;u<=n;u++) {
memset(vis,0,sizeof(vis));
if(find(u)) ret ++;
}
return ret;
}
int main() {
int N;
while(~scanf("%d",&N) && N) {
memset(mapl,0,sizeof(map));
memset(mapr,0,sizeof(mapr));
for(int i=0;i<N;i++) scanf("%s",map[i]);
n = m = 0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(map[i][j] == 'X') mapl[i][j] = mapr[i][j] = -1;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) {
while(mapr[i][j]==-1&&j<N) j++;
n ++;
while(mapr[i][j]!=-1&&j<N) mapr[i][j++] = n;
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) {
while(mapl[j][i]==-1&&j<N) j++;
m ++;
while(mapl[j][i]!=-1&&j<N) mapl[j++][i] = m;
}
memset(g,0,sizeof(g));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) {
if(mapr[i][j]!=-1&&mapl[i][j]!=-1) g[mapr[i][j]][mapl[i][j]] = 1;
}
int ans = hungry();
printf("%d\n",ans);
}
return 0;
}

posted @ 2012-10-22 05:03 YouAreInMyHeart 阅读(79) | 评论 (0)编辑 收藏