YAIMH1993的笔记
如果奇迹木有出现,就去创造一个
posts - 29,comments - 0,trackbacks - 0
三分
posted @ 2012-10-24 01:04 YouAreInMyHeart 阅读(98) | 评论 (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];
    }
    return top; // 返回凸包中点的个数
}

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)编辑 收藏
好吧,我承认我真的没有其他办法了,代码太长,C++博客可能都爆栈了,所以省略了一些内容。。。。。。
如果有好的方法希望有大神指教
#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 阅读(54) | 评论 (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 阅读(51) | 评论 (0)编辑 收藏

#include <cstdio>
#include <cstring>
using namespace std;
int g[33][33],linky[33];
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;
            if(linky[v]==-1 || find(linky[v])) {
                linky[v] = u;
                return true;   
            }   
        }
    return false;
}
int hungry() {
    int ret = 0;
    memset(linky,-1,sizeof(linky));
    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)编辑 收藏
仅列出标题  下一页