|
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class MountainRoad
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
public:
double findDistance(vector <int> start, vector <int> finish)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
sort(start.begin(),start.end());
sort(finish.begin(),finish.end());
return sqrt(2.0)*(finish.back()-start.front());
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
using namespace std;
class OddDivisors
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
public:
long long findSum(int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
long long sum=0LL;
for(;n;n/=2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
long long k=(n+1)/2;
sum+=k*k;
}
return sum;
}
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int x,y;
point(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
x=a;
y=b;
}
};
vector<point>A,B;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector<point> find(int a)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
vector<point>v;
int x,y;
for(x=0;x*x<=a;x++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
y=int( sqrt((1.0*a-x*x)) );
if( (x*x+y*y)==a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
v.push_back( point(x,y) );
v.push_back( point(x,-y) );
}
}
return v;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
class MaxTriangle
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
public:
double calculateArea(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
A=find(a);
B=find(b);
int i,j;
double res=-1;
for(i=0;i<A.size();i++)
for(j=0;j<B.size();j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
double area=abs((A[i].x*B[j].y-A[i].y*B[j].x))/2.0;
if(area&&res<area)
res=area;
}
return res;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
};
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int size=1000005;
bool ok[size];
int ph[size];
int prime[size];
__int64 sum[size];
int pn;
int n;
void getph()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
pn=0;
for(i=2;i<size;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(!ok[i])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
prime[pn++]=i;
ph[i]=i-1;
}
for(j=0;(j<pn)&&(i*prime[j]<size);j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ok[i*prime[j]]=1;
if((i%prime[j])==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
ph[i*prime[j]]=ph[i]*prime[j];
break;
}
else
ph[i*prime[j]]=ph[i]*(prime[j]-1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
ph[1]=1;
getph();
for(int i=2;i<size;i++)
sum[i]=sum[i-1]+ph[i];
while(scanf("%d",&n)!=EOF&&(n!=0))
printf("%I64d\n",sum[n]);
return 0;
}
#include <iostream>
using namespace std;
const int maxn=1005;
const int M=28;
int map[M][M];
int chu[M],ru[M];
bool vis[M];
int n;
int sum;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void dfs(int s)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
vis[s]=true;
sum++;
int i;
for(i=0;i<26;i++)
if(map[s][i]&&!vis[i])
dfs(i);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int T;
scanf("%d",&T);
while(T--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
memset(map,0,sizeof(map));
memset(chu,0,sizeof(chu));
memset(ru,0,sizeof(ru));
memset(vis,0,sizeof(vis));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
char word[maxn];
scanf("%s",&word);
int len=strlen(word);
map[word[0]-'a'][word[len-1]-'a']=1;
chu[word[0]-'a']++;
ru[word[len-1]-'a']++;
}
int n0=0,n1=0,n2=0,n3=0;
int s=-1,e=-1;
for(i=0;i<26;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(chu[i]==0&&ru[i]==0)
continue;
n0++;
if((ru[i]-chu[i])==1)
n2++;
if((chu[i]-ru[i])==0)
n3++;
if((chu[i]-ru[i])==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
s=i;
n1++;
}
e=i;
}
sum=0;
if(s!=-1)
dfs(s);
else
dfs(e);
if(sum!=n0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("The door cannot be opened.\n");
continue;
}
if( (n1==1&&n2==1&&n3==(n0-2)) || (n0==n3) )
printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
}
return 0;
}
#include <iostream>
using namespace std;
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int ball[100001],n;
while(scanf("%d",&n)!=EOF&&n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
memset(ball,0,sizeof(ball));
int i;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int a,b;
scanf("%d%d",&a,&b);
ball[a]++;
ball[b+1]--;
}
int sum=0;
for(i=1;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
sum+=ball[i];
printf("%d ",sum);
}
printf("%d\n",sum+ball[i]);
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1000;
struct group
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int h,m,t;
};
group team[maxn];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int n2,n4,n6;
while(scanf("%d%d%d",&n2,&n4,&n6)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(n2==0&&n4==0&&n6==0)
break;
char time[6];
int cnt=0;
while(scanf("%s",&time)!=EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(strcmp(time,"#")==0)
break;
int t;
scanf("%d",&t);
team[cnt].t=t;
team[cnt].h=(time[0]-'0')*10+(time[1]-'0');
team[cnt].m=(time[3]-'0')*10+(time[4]-'0');
cnt++;
}
int i,j;
vector<group> team12,team34,team56;
__int64 sum=0;
for(i=0;i<cnt;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int len;
group tmp;
if(team[i].t==1||team[i].t==2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len=team12.size();
if(len<n2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
team12.push_back(team[i]);
sum+=team[i].t;
continue;
}
tmp=team12.front();
int usetime=(team[i].h-tmp.h)*60+(team[i].m-tmp.m);
group fuck;
fuck=team12.back();
if(((team[i].h-fuck.h)*60+(team[i].m-fuck.m))<=0)
continue;
if(usetime<0)
continue;
if(usetime<30)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
team[i].h=tmp.h+(tmp.m+30)/60;
team[i].m=(tmp.m+30)%60;
}
team12.erase(team12.begin());
team12.push_back(team[i]);
sum+=team[i].t;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(team[i].t==3||team[i].t==4)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
len=team34.size();
if(len<n4)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
team34.push_back(team[i]);
sum+=team[i].t;
continue;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tmp=team34.front();
int usetime=(team[i].h-tmp.h)*60+(team[i].m-tmp.m);
group fuck;
fuck=team12.back();
if(((team[i].h-fuck.h)*60+(team[i].m-fuck.m))<=0)
continue;
if(usetime<0)
continue;
if(usetime<30)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
team[i].h=tmp.h+(tmp.m+30)/60;
team[i].m=(tmp.m+30)%60;
}
team34.erase(team34.begin());
team34.push_back(team[i]);
sum+=team[i].t;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(team[i].t==5||team[i].t==6)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
len=team56.size();
if(len<n6)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
team56.push_back(team[i]);
sum+=team[i].t;
continue;
}
tmp=team56.front();
int usetime=(team[i].h-tmp.h)*60+(team[i].m-tmp.m);
group fuck;
fuck=team12.back();
if(((team[i].h-fuck.h)*60+(team[i].m-fuck.m))<=0)
continue;
if(usetime<0)
continue;
if(usetime<30)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
team[i].h=tmp.h+(tmp.m+30)/60;
team[i].m=(tmp.m+30)%60;
}
team56.erase(team56.begin());
team56.push_back(team[i]);
sum+=team[i].t;
}
}
printf("%I64d\n",sum);
}
return 0;
}
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int maxn=32;
int n,k,m;
struct matrix
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int m[maxn][maxn];
};
matrix mat;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
matrix operator*(const matrix &a,const matrix &b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
matrix res;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
res.m[i][j]=0;
for(k=1;k<=n;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
res.m[i][j]+=a.m[i][k]*b.m[k][j];
res.m[i][j]%=m;
}
}
return res;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
matrix operator+(const matrix &a,const matrix &b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
matrix res;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
res.m[i][j]=(a.m[i][j]+b.m[i][j])%m;
return res;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
matrix power(int k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
matrix temp,res;
if(k==1)
return mat;
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp=power(k/2);
res=temp*temp;
if(k%2==1)
res=res*mat;
return res;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
matrix solve(int k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
matrix temp,res;
if(k==1)
return mat;
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
res=solve(k/2);
if(k%2==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp=power(k/2+1);
res=temp*res+res+temp;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
res=power(k/2)*res+res;
}
return res;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void printf(const matrix & m)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=1;j<n;j++)
printf("%d ",m.m[i][j]);
printf("%d\n",m.m[i][j]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
scanf("%d%d%d",&n,&k,&m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&mat.m[i][j]);
matrix temp=solve(k);
printf(temp);
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int M=20000+5;
const int Maxn=100000+5;
int skill[M];
int tree[Maxn];
int lmax[M],lmin[M];
int rmax[M],rmin[M];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int lowbit(int t) {return t&(-t);}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void add(int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
while(i<Maxn)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tree[i]++;
i+=lowbit(i);
}
}
int sum(int i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int tot=0;
while(i>0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tot+=tree[i];
i-=lowbit(i);
}
return tot;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int T;
scanf("%d",&T);
while(T--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&skill[i]);
memset(tree,0,sizeof(tree));
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
lmin[i]=sum(skill[i]);
lmax[i]=i-lmin[i]-1;
add(skill[i]);
}
memset(tree,0,sizeof(tree));
for(i=n;i>=1;i--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
rmin[i]=sum(skill[i]);
rmax[i]=sum(Maxn)-rmin[i];
add(skill[i]);
}
__int64 ans=0;
for(i=1;i<=n;i++)
ans+=lmax[i]*rmin[i]+lmin[i]*rmax[i];
printf("%I64d\n",ans);
}
return 0;
}
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int maxn=205;
int qun[maxn];
char res[maxn];
char str[maxn];
int t[maxn];
int n;
void getT()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(t[i]==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int cnt=1;
int top=-1;
int same[maxn];
int pos=qun[i];
while(pos!=i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
same[++top]=pos;
pos=qun[pos];
cnt++;
}
t[i]=cnt;
for(j=0;j<=top;j++)
t[same[j]]=cnt;
}
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(scanf("%d",&n)!=EOF&&n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int i,j;
for(i=1;i<=n;i++)
scanf("%d",&qun[i]);
memset(t,0,sizeof(t));
getT();
int k;
while(scanf("%d",&k)!=EOF&&k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
memset(res,'\0',sizeof(res));
memset(str,'\0',sizeof(str));
gets(str);
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int tmp=i;
for(j=0;j<k%t[i];j++)
tmp=qun[tmp];
if(str[i]=='\0') res[tmp]=' ';
else res[tmp]=str[i];
}
printf("%s\n",res+1);
}
printf("\n");
}
return 0;
}
#include <iostream>
using namespace std;
#define min(a,b)(a<b?a:b)
#define max(a,b)(a>b?a:b)
const int maxn=15;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct point {int x,y;};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct line {point a,b;};
line straw[maxn];
bool link[maxn][maxn];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int multi(point p1,point p2,point p0) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool across(line u,line v)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if( max(u.a.x,u.b.x)>=min(v.a.x,v.b.x)&&
max(v.a.x,v.b.x)>=min(u.a.x,u.b.x)&&
max(u.a.y,u.b.y)>=min(v.a.y,v.b.y)&&
max(v.a.y,v.b.y)>=min(u.a.y,u.b.y)&&
(multi(v.a,u.b,u.a)*multi(u.b,v.b,u.a)>=0)&&
(multi(u.a,v.b,v.a)*multi(v.b,u.b,v.a)>=0) )
return 1;
else return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void check()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
if(link[i][k])
for(j=1;j<=n;j++)
if(link[k][j]) link[i][j]=true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
while(scanf("%d",&n)!=EOF&&n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int i,j;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int sx,sy,ex,ey;
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
straw[i].a.x=sx;straw[i].a.y=sy;
straw[i].b.x=ex;straw[i].b.y=ey;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
link[i][j]=link[j][i]=across(straw[i],straw[j]);
check();
int cx,cy;
while(scanf("%d%d",&cx,&cy)!=EOF&&cx!=0&&cy!=0)
if(link[cx][cy])
printf("CONNECTED\n");
else printf("NOT CONNECTED\n");
}
return 0;
}
#include <iostream>
using namespace std;
int r[301][301];
int c[301][301];
int a[301][301];
int b[301][301];
int rr,cc;
bool check(int i,int j,int k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if(r[i][j+k-1]-r[i][j-1]==k)
if(r[i+k-1][j+k-1]-r[i+k-1][j-1]==k)
if(c[i+k-1][j]-c[i-1][j]==k)
if(c[i+k-1][j+k-1]-c[i-1][j+k-1]==k)
return 1;
return 0;
}
void slove()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j,k;
int cnt=0;
for(i=1;i<=rr;i++)
for(j=1;j<=cc;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(k=2;k<=rr&&k<=cc;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(check(i,j,k))
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int sum=b[i+k-1][j+k-1]-b[i-1][j+k-1]-b[i+k-1][j-1]+b[i-1][j-1];
int cnt_1=sum-(k-1)*4;
int cnt_0=(k-2)*(k-2)-cnt_1;
if(abs(cnt_1-cnt_0)<=1)
cnt++;
}
}
}
printf("%d\n",cnt);
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int T;
scanf("%d",&T);
while(T--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d%d",&rr,&cc);
int i,j;
for(i=1;i<=rr;i++)
for(j=1;j<=cc;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d",&a[i][j]);
b[i][j]=b[i-1][j]+b[i][j-1]+a[i][j]-b[i-1][j-1];//0 0->i j
r[i][j]=r[i][j-1]+a[i][j];//r
c[i][j]=c[i-1][j]+a[i][j];//c
}
slove();
}
return 0;
}
|