求 n (1 <= n <= 100)
个矩形的面积并。 题目链接：
http://poj.org/problem?id=1151
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 210;
const double eps = 1e-9;
struct line_t
{
double l_x, r_x, y;
bool flag;
};
bool cmp(const line_t &a, const line_t &b)
{
return a.y < b.y;
}
bool is_equal(const double &a, const double &b)
{
return abs(a - b) < eps;
}
int n;
double x[maxn];
int cnt_x, cnt_line;
line_t line[maxn];
int main()
{
int num = 0;
while(scanf("%d", &n) != EOF && n)
{
cnt_x = 0;
cnt_line = 0;
for(int i = 0; i < n; ++i)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
x[cnt_x++] = x1;
x[cnt_x++] = x2;
line[cnt_line].flag = false;
line[cnt_line].l_x = x1;
line[cnt_line].r_x = x2;
line[cnt_line++].y = y1;
line[cnt_line].flag = true;
line[cnt_line].l_x = x1;
line[cnt_line].r_x = x2;
line[cnt_line++].y = y2;
}
sort(line,line + cnt_line, cmp);
sort(x, x + cnt_x);
cnt_x = unique(x, x + cnt_x, is_equal) - x;
double area = 0.0;
for(int i = 0; i < cnt_x - 1; ++i)
{
int cnt = 0;
double now_y;
for(int j = 0; j < cnt_line; ++j)
if(line[j].l_x <= x[i] && line[j].r_x >= x[i + 1])
{
if(cnt == 0) now_y = line[j].y;
if(!line[j].flag) ++cnt;
else --cnt;
if(cnt == 0) area += (x[i + 1] - x[i]) * (line[j].y - now_y);
}
}
printf("Test case #%d\n", ++num);
printf("Total explored area: %.2lf\n\n", area);
}
return 0;
}
posted @
2011-10-08 10:59 wuxu 阅读(258) |
评论 (0) |
编辑 收藏#include<iostream>
#include<string>
#include<stack>
using namespace std;
string DecToBinary(const string &dec)
{
int i,len,sta;
stack<int> s;
len=dec.length();
int *num=new int[len+1];
for(i=0;i<len;++i)
{
num[i]=dec[i]-'0';
}
while(true)
{
sta=len;
for(i=0;i<len;++i)
{
if(num[i]!=0)
{
sta=i;
break;
}
}
if(sta==len) break;
int remain=0;
for(i=sta;i<len;++i)
{
remain=remain*10+num[i];
num[i]=remain/2;
remain=remain%2;
}
s.push(remain);
}
string ans;
while(!s.empty())
{
ans+=s.top()+'0';
s.pop();
}
if(ans.length()==0)
ans="0";
delete [] num;
return ans;
}
int main()
{
string dec,bin;
while(cin>>dec)
{
bin=DecToBinary(dec);
cout<<bin<<endl;
}
return 0;
}
posted @
2011-07-31 15:37 wuxu 阅读(870) |
评论 (0) |
编辑 收藏#include<iostream>
#include<string>
using namespace std;
string BigIntegerMod(const string &str1,const string &str2) // str1%str2
{
int i;
int len,len1,len2,index;
bool flag;
len1=str1.length();
len2=str2.length();
len=len1-len2;
if(len<0) return str1;
int *num1=new int[len1+2];
int *num2=new int[len2+2];
memset(num1,0,sizeof(int)*(len1+2));
memset(num2,0,sizeof(int)*(len2+2));
for(i=len1-1,index=0;i>=0;--i)
{
num1[index++]=str1[i]-'0';
}
for(i=len2-1,index=0;i>=0;--i)
{
num2[index++]=str2[i]-'0';
}
while(true)
{
for(i=len1-1;i>=0;i--)
{
if(num1[i])
{
len1=i+1;
break;
}
if(i==0) len1=0;
}
len=len1-len2;
if(len<0) break;
flag=false;
index=0;
for(i=len1-1;i>=len;i--)
{
if(num1[i]==num2[i-len]) continue;
else if(num1[i]<num2[i-len])
{
flag=true;
break;
}
else break;
}
if(flag) --len;
if(len<0) break;
while(++index)
{
flag=false;
for(i=len1-1;i>=len;i--)
{
if(num1[i]==num2[i-len]) continue;
else if(num1[i]<num2[i-len])
{
flag=true;
break;
}
else break;
}
if(flag)
{
--index;
break;
}
for(i=len;i<len1;i++)
{
num1[i]-=num2[i-len];
if(num1[i]<0)
{
num1[i]+=10;
--num1[i+1];
}
}
}
if(index==0) break;
}
string ans;
flag=false;
for(i=len1;i>=0;--i)
{
if(flag||num1[i])
{
flag=true;
ans+='0'+num1[i];
}
}
if(!flag) ans="0";
delete [] num1;
delete [] num2;
return ans;
}
int main()
{
string str,str1,str2;
while(cin>>str1>>str2)
{
str=BigIntegerMod(str1,str2);
cout<<str<<endl;
}
return 0;
}
posted @
2011-07-31 15:24 wuxu 阅读(521) |
评论 (0) |
编辑 收藏
摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include<iostream>#include<string>using namespace std;string BigIntegerDiv(...
阅读全文
posted @
2011-07-31 15:22 wuxu 阅读(1023) |
评论 (0) |
编辑 收藏
#include<iostream>
#include<string>
using namespace std;
string BigIntegerMult(const string &str1,const string &str2)
{
string ans;
int index,i,j;
int len1,len2;
len1=str1.length();
len2=str2.length();
unsigned int *total=new unsigned int[len1+len2+2];
unsigned int *integ1=new unsigned int[len1];
unsigned int *integ2=new unsigned int[len2];
index=0;
for(i=len1-1;i>=0;--i)
{
integ1[index++]=str1[i]-'0';
}
index=0;
for(i=len2-1;i>=0;--i)
{
integ2[index++]=str2[i]-'0';
}
memset(total,0,sizeof(unsigned int)*(len1+len2+2));
for(i=0;i<len1;i++)
for(j=0;j<len2;j++)
{
total[i+j]+=integ1[i]*integ2[j];
}
for(i=0;i<len1+len2+1;i++)
{
if(total[i]>9)
{
total[i+1]+=total[i]/10;
total[i]=total[i]%10;
}
}
bool flag=false;
for(i=len1+len2+1;i>=0;i--)
{
if(flag||total[i])
{
flag=true;
ans+=total[i]+'0';
}
}
if(!flag)
ans+='0';
delete [] integ1;
delete [] integ2;
delete [] total;
return ans;
}
int main()
{
string str1,str2,str;
cin>>str1>>str2;
str=BigIntegerMult(str1,str2);
cout<<str<<endl;
return 0;
}
posted @
2011-06-09 16:51 wuxu 阅读(365) |
评论 (0) |
编辑 收藏
摘要: /**//* sap+gap优化+当前弧优化, 采用邻接表+反向弧指针 时间复杂度:O(mn^2)*/#include<iostream>using namespace std;const int maxnode = 1024...
阅读全文
posted @
2011-05-10 13:17 wuxu 阅读(761) |
评论 (0) |
编辑 收藏
摘要: /**//* sap+gap优化,采用邻接矩正 时间复杂度:O(mn^2)*/#include<iostream>#include<queue>using namespace std;const int msize=205; &nbs...
阅读全文
posted @
2011-05-10 13:12 wuxu 阅读(541) |
评论 (0) |
编辑 收藏
/**//*
EdmondsKarp算法，O(m^2n)
*/
#include<iostream>
#include<queue>
using namespace std;
const int maxn=205;
const int inf=0x7fffffff;
int r[maxn][maxn]; //残留网络，初始化为原图
bool visit[maxn];
int pre[maxn];
int m,n;
bool bfs(int s,int t) //寻找一条从s到t的增广路，若找到返回true
{
int p;
queue<int > q;
memset(pre,-1,sizeof(pre));
memset(visit,false,sizeof(visit));
pre[s]=s;
visit[s]=true;
q.push(s);
while(!q.empty())
{
p=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(r[p][i]>0&&!visit[i])
{
pre[i]=p;
visit[i]=true;
if(i==t) return true;
q.push(i);
}
}
}
return false;
}
int EdmondsKarp(int s,int t)
{
int flow=0,d,i;
while(bfs(s,t))
{
d=inf;
for(i=t;i!=s;i=pre[i])
d=d<r[pre[i]][i]? d:r[pre[i]][i];
for(i=t;i!=s;i=pre[i])
{
r[pre[i]][i]-=d;
r[i][pre[i]]+=d;
}
flow+=d;
}
return flow;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
int u,v,w;
memset(r,0,sizeof(r));/**////
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
r[u][v]+=w;
}
printf("%d\n",EdmondsKarp(1,n));
}
return 0;
}posted @
2011-05-10 13:10 wuxu 阅读(321) |
评论 (0) |
编辑 收藏
摘要: /**//* dinic算法，边表存储（仿指针），实用于稀疏图，O(mn^2)*/#include<iostream>using namespace std;const int maxn=205; //最大定点数const int maxm=205...
阅读全文
posted @
2011-05-10 13:07 wuxu 阅读(308) |
评论 (0) |
编辑 收藏
摘要: /**//* dinic算法,邻接矩正,O(mn^2)*/#include<iostream>#include<algorithm>#include<queue>using namespace std;const int maxnode=205;const int&n...
阅读全文
posted @
2011-05-10 13:05 wuxu 阅读(367) |
评论 (0) |
编辑 收藏