yzhw 2012-02-22 15:58 发表评论

 1 Show Code - Run ID 1166912
 2 
 3 Submit Time: 2012-02-18 01:33:04     Language: GNU C     Result: Accepted
 4     Pid: 3124     Time: 0.00 sec.     Memory: 852 K.     Code Length: 0.6 K.
 5 # include <stdio.h>
 6 # define cross(x1,y1,x2,y2) (x1)*(y2)-(x2)*(y1)
 7 # define get_aera(x0,y0,x1,y1,x2,y2) (cross((x1)-(x0),(y1)-(y0),(x2)-(x0),(y2)-(y0)))
 8 int main()
 9 {
10     int n;
11     while(scanf("%d",&n)!=EOF&&n)
12     {
13        int i;
14       
15            double x[3],y[3],aera=0;
16            scanf("%lf%lf",&x[2],&y[2]);
17            for(i=1;i<n;i++)
18            {
19                scanf("%lf%lf",&x[i%2],&y[i%2]);
20                if(i>1) aera+=get_aera(x[2],y[2],x[(i+1)%2],y[(i+1)%2],x[i%2],y[i%2]);
21            }
22            aera*=0.5;
23            if(aera<0) aera=-aera;
24            printf("%.0f\n",aera+1e-8);
25        
26     }
27     return 0;
28 }

yzhw 2012-02-18 01:34 发表评论

 2 
 3 Problem: 3905        User: yzhw
 4 Memory: 16168K        Time: 2297MS
 5 Language: GCC        Result: Accepted
 6 Source Code
 7 # include <stdio.h>
 8 # include <stdlib.h>
 9 # include <string.h>
10 # define N 2000
11 # define M 1000000*2
12 # define min(a,b) ((a)<(b)?(a):(b))
13 # define abs(a) ((a)>0?(a):-(a))
14 int n,m;
15 int p,nxt[M],g[N],v[M];
16 int stack[N],sp,dfn,low[N];
17 void insert(int a,int b)
18 {
19     v[p]=b;
20     nxt[p]=g[a];
21     g[a]=p++;
22 }
23 int dfs(int pos)
24 {
25     int minnum=dfn++;
26     int p;
27     stack[sp++]=pos;
28     low[pos]=minnum;
29     for(p=g[pos];p!=-1;p=nxt[p])
30     {
31       if(low[v[p]]==-1)
32         if(!dfs(v[p])) return 0;
33       minnum=min(minnum,low[v[p]]);
34     }
35     if(minnum<low[pos]) low[pos]=minnum;
36     else
37     {
38         do
39         {
40             low[stack[sp-1]]=N;
41             if(abs(stack[sp-1]-pos)==n) return 0;
42             sp--;
43         }while(stack[sp]!=pos);
44     }
45     return 1;
46 }
47 int main()
48 {
49     while(scanf("%d%d",&n,&m)!=EOF)
50     {
51         int i,flag=1;
52         memset(g,-1,sizeof(g));
53         p=0;
54         for(i=0;i<m;i++)
55         {
56             char str1[32],str2[32];
57             int num1,num2;
58             scanf("%s%s",str1,str2);
59             num1=atoi(str1+1)-1;
60             num2=atoi(str2+1)-1;
61             if(*str1=='+'&&*str2=='+')
62             {
63                 insert(num1+n,num2);
64                 insert(num2+n,num1);
65             }
66             else if(*str1=='-'&&*str2=='-')
67             {
68                 insert(num1,num2+n);
69                 insert(num2,num1+n);
70             }
71             else if(*str1=='+'&&*str2=='-')
72             {
73                 insert(num1+n,num2+n);
74                 insert(num2,num1);
75             }
76             else
77             {
78                 insert(num1,num2);
79                 insert(num2+n,num1+n);
80             }
81         }
82         memset(low,-1,sizeof(low));
83         dfn=sp=0;
84         for(i=0;i<2*n&&flag;i++)
85             if(low[i]==-1)
86                 if(!dfs(i)) flag=0;
87         printf("%d\n",flag);
88     }
89     return 0;
90 }

yzhw 2012-02-17 02:38 发表评论

 1 # include <cstdio>
 2 # include <map>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 int pa[2000],pp=0,sa[10],sp=0;
 7 int refer[5][10001];
 8 void make_prime()
 9 {
10     bool used[10001];
11     memset(used,true,sizeof(used));
12     for(int i=2;i<=10000;i++)
13          if(used[i])
14          {
15              pa[pp++]=i;
16              for(int j=2*i;j<=10000;j+=i)
17                 used[j]=false;
18          }
19 }
20 void spilt(int n)
21 {
22     sp=0;
23     for(int i=0;i<pp&&n!=1;i++)
24         if(n%pa[i]==0)
25         {
26             sa[sp++]=pa[i];
27             while(n%pa[i]==0)
28                 n/=pa[i];
29         }
30 }
31 void putmap(int n)
32 {
33     spilt(n);
34     for(int i=1;i<(1<<sp);i++)
35     {
36         int n1=0,n2=1;
37         for(int j=0;j<5;j++)
38             if(i&(1<<j))
39                 n1++,n2*=sa[j];
40         refer[n1-1][n2]++;
41     }
42 }
43 long long c(int n)
44 {
45     return (long long)n*(n-1)*(n-2)*(n-3)/4/3/2;
46 }
47 long long getans(int n)
48 {
49     long long ans=c(n);
50     for(int i=0;i<5;i++)
51     {
52         bool flag=false;
53         for(int j=1;j<=10000;j++)
54             if(refer[i][j]>=4)
55                 flag=true,
56                 ans+=c(refer[i][j])*(i%2?1ll:-1ll);
57         if(!flag)break;
58     }
59     return ans;
60 }
61 int main()
62 {
63     int n;
64     make_prime();
65     while(scanf("%d",&n)!=EOF)
66     {
67         memset(refer,0,sizeof(refer));
68         for(int i=0;i<n;i++)
69         {
70             int t;
71             scanf("%d",&t);
72             putmap(t);
73         }
74         printf("%lld\n",getans(n));
75     }
76     return 0;
77 }

yzhw 2012-02-17 02:03 发表评论

 1 # include <cstdio>
 2 # include <set>
 3 using namespace std;
 4 struct node
 5 {
 6    int height,id;
 7    node(int h,int i):height(h),id(i){}
 8    bool operator<(const node &pos) const
 9    {
10        if(height!=pos.height) return height<pos.height;
11        else return id<pos.id;
12    }
13 };
14 set<node> q;
15 int dp[100005];
16 int main()
17 {
18      int n;
19      while(scanf("%d",&n)!=EOF)
20      {
21         q.clear();
22         for(int i=0;i<n;i++)
23         {
24             int t;
25             scanf("%d",&t);
26             set<node>::iterator it=q.lower_bound(node(t,-1));
27             int ans;
28             if(it==q.begin())
29               ans=1;
30             else
31               ans=dp[(--it)->id]+1;
32             it=q.lower_bound(node(t,-1));
33             if(it!=q.end()&&it->height==t) 
34                  it=q.erase(it);
35             while(it!=q.end()&&dp[it->id]<=ans) 
36                  it=q.erase(it);
37             q.insert(node(t,i)); 
38             dp[i]=ans;
39         }
40         printf("%d\n",dp[q.rbegin()->id]);
41      }
42      return 0;
43 }
44 

yzhw 2012-02-09 19:33 发表评论

  1 Source Code
  2 
  3 Problem: 3943        User: yzhw
  4 Memory: 656K        Time: 188MS
  5 Language: G++        Result: Accepted
  6 Source Code
  7 # include <cstdio>
  8 # include <vector>
  9 # include <cstring>
 10 # include <map>
 11 using namespace std;
 12 # define N 1005
 13 # define min(a,b) ((a)<(b)?(a):(b))
 14 # define max(a,b) ((a)>(b)?(a):(b))
 15 struct line
 16 {
 17     int x1,y1,x2,y2;
 18 }l[N];
 19 bool in(int x,int y,const line &pos)
 20 {
 21     if(x>=min(pos.x1,pos.x2)&&x<=max(pos.x1,pos.x2)&&
 22        y>=min(pos.y1,pos.y2)&&y<=max(pos.y1,pos.y2)&&
 23        (pos.y2-pos.y1)*(pos.x2-x)==(pos.x2-pos.x1)*(pos.y2-y))
 24        return true;
 25     else return false;
 26 }
 27 int cross(const line &a,const line &b)
 28 {
 29     if(a.x1==b.x1&&a.y1==b.y1||
 30         a.x2==b.x1&&a.y2==b.y1||
 31         a.x1==b.x2&&a.y1==b.y2||
 32         a.x2==b.x2&&a.y2==b.y2) return 1;
 33     else if(in(a.x1,a.y1,b)||in(a.x2,a.y2,b)||in(b.x1,b.y1,a)||in(b.x2,b.y2,a)) return 2;
 34     else return 0;
 35 }
 36 int cross(int x1,int y1,int x2,int y2)
 37 {
 38     return x1*y2-x2*y1;
 39 }
 40 struct node
 41 {
 42     vector<line> data;
 43     int type() const
 44     {
 45         int num[3]={0,0,0};
 46         for(int i=0;i<data.size();i++)
 47             for(int j=i+1;j<data.size();j++)
 48                 num[cross(data[i],data[j])]++;
 49         if(num[1]==4&&num[2]==0)
 50         {
 51             if(data.size()==4) return 0;
 52             else
 53             {
 54                 int target=-1,x1,y1,x2,y2;
 55                 for(int i=0;i<data.size();i++)
 56                 {
 57                     bool flag=true;
 58                     for(int j=0;j<data.size()&&flag;j++)
 59                         if(j!=i&&(data[i].x1==data[j].x1&&data[i].y1==data[j].y1||data[i].x1==data[j].x2&&data[i].y1==data[j].y2))
 60                             flag=false;
 61                     if(flag)
 62                     {
 63                         target=i;
 64                         x1=data[i].x2,y1=data[i].y2;
 65                         x2=data[i].x1,y2=data[i].y1;
 66                         break;
 67                     }
 68                     flag=true;
 69                     for(int j=0;j<data.size()&&flag;j++)
 70                         if(j!=i&&(data[i].x2==data[j].x1&&data[i].y2==data[j].y1||data[i].x2==data[j].x2&&data[i].y2==data[j].y2))
 71                             flag=false;
 72                     if(flag)
 73                     {
 74                         target=i;
 75                         x1=data[i].x1,y1=data[i].y1;
 76                         x2=data[i].x2,y2=data[i].y2;
 77                         break;
 78                     }
 79                 }
 80                 for(int i=0;i<data.size();i++)
 81                     if(i!=target)
 82                     {
 83                         if(data[i].x1==x1&&data[i].y1==y1)
 84                             return cross(data[i].x2-data[i].x1,data[i].y2-data[i].y1,x1-x2,y1-y2)<0?5:2;
 85                         else if(data[i].x2==x1&&data[i].y2==y1)
 86                             return cross(data[i].x1-data[i].x2,data[i].y1-data[i].y2,x1-x2,y1-y2)<0?5:2;
 87                     }
 88             }
 89             printf("wa!\n");
 90             while(true);
 91         }
 92         else if(num[1]==0&&num[2]==0)
 93             return 1;
 94         else if(num[1]==4&&num[2]==0)
 95             return 2;
 96         else if(num[1]==2&&num[2]==1)
 97             return 3;
 98         else if(num[1]==1&&num[2]==1)
 99             return 4;
100         else if(num[1]==4&&num[2]==1)
101             return 6;
102         else if(num[1]==2&&num[2]==0)
103             return 7;
104         else if(num[1]==4&&num[2]==2)
105             return 8;
106         else if(num[1]==3&&num[2]==1)
107             return 9;
108     }
109 };
110 map<int,node> data;
111 int n,set[N],ans[10];
112 int find(int pos)
113 {
114     if(set[pos]==pos) return pos;
115     else return set[pos]=find(set[pos]);
116 }
117 int main()
118 {
119     while(scanf("%d",&n)!=EOF&&n)
120     {
121         data.clear();
122         memset(ans,0,sizeof(ans));
123         for(int i=0;i<n;i++)
124         {
125             set[i]=i;
126             scanf("%d%d%d%d",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
127             for(int j=0;j<i;j++)
128                 if(cross(l[i],l[j])&&find(i)!=find(j))
129                     set[find(i)]=find(j);
130         }
131         for(int i=0;i<n;i++)
132             data[find(i)].data.push_back(l[i]);
133         for(map<int,node>::iterator i=data.begin();i!=data.end();i++)
134             ans[i->second.type()]++;
135         printf("%d",ans[0]);
136         for(int i=1;i<10;i++)
137             printf(" %d",ans[i]);
138         printf("\n");
139     }
140     return 0;
141 }

yzhw 2012-01-14 19:57 发表评论

yzhw 2011-10-18 02:17 发表评论

 1 # include <cstdio>
 2 # include <utility>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <functional>
 6 # include <set>
 7 # include <cstdlib>
 8 # include <map>
 9 using namespace std;
10 struct node
11 {
12     int p[3];
13     bool operator<(const node &pos) const
14     {
15         for(int i=0;i<3;i++)
16             if(p[i]!=pos.p[i]) 
17                 return p[i]<pos.p[i];
18         return false;
19     }
20 };
21 pair<int,int> data[1000][2];
22 set<pair<pair<int,int>,pair<int,int> > > r1;
23 map<node,int> r2;
24 int main()
25 {
26     int test;
27     scanf("%d",&test);
28     while(test--)
29     {
30        int n,m,p=0;
31        char str[128];
32        scanf("%d%d",&n,&m);
33        r1.clear();r2.clear();
34        while(m--)
35        {
36            scanf("%s",str);
37            char *t=strtok(str,",");
38            data[p][0].first=(*t)-'X';
39            data[p][0].second=atoi(t+2);
40            t=strtok(NULL," ");
41            data[p][1].first=(*t)-'X';
42            data[p][1].second=atoi(t+2);
43            if(data[p][0].first>data[p][1].first) swap(data[p][0],data[p][1]);
44            pair< pair<int,int>,pair<int,int> > tt;
45            tt.first=data[p][0];
46            tt.second=data[p][1];
47            if(data[p][0].second>=1&&data[p][0].second<=n&&data[p][1].second>=1&&data[p][1].second<=n&&r1.find(tt)==r1.end()) p++,r1.insert(tt);
48        }
49        m=p;
50        for(int i=0;i<m;i++)
51         for(int j=i+1;j<m;j++)
52           if(data[i][0]==data[j][0]&&data[i][1].first!=data[j][1].first||
53              data[i][1]==data[j][0]&&data[i][0].first!=data[j][1].first||
54              data[i][0]==data[j][1]&&data[i][1].first!=data[j][0].first||
55              data[i][1]==data[j][1]&&data[i][0].first!=data[j][0].first)
56           {
57               node t;
58               t.p[data[i][0].first]=data[i][0].second;
59               t.p[data[i][1].first]=data[i][1].second;
60               t.p[data[j][0].first]=data[j][0].second;
61               t.p[data[j][1].first]=data[j][1].second;
62               r2[t]++;
63           }
64        int total=m*n;
65        for(map<node,int>::iterator i=r2.begin();i!=r2.end();i++)
66            if(i->second==1) total--;
67            else total-=2;
68        printf("%d\n",total);
69     }
70     //system("pause");
71     return 0;
72 } 
73 

yzhw 2011-10-03 00:06 发表评论

yzhw 2011-09-30 08:51 发表评论

yzhw 2011-09-30 08:44 发表评论