Submission #3056020
Source Code Expand
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define N (1001)
using namespace std;
struct Vector
{
double x,y;
Vector(double X=0,double Y=0)
{
x=X,y=Y;
}
};
typedef Vector Point;
const double pi= acos(-1.0);
Vector operator + (Vector A,Vector B) {return ((Vector){A.x+B.x,A.y+B.y});}
Vector operator - (Vector A,Vector B) {return ((Vector){A.x-B.x,A.y-B.y});}
Vector operator * (Vector A,double p) {return ((Vector){A.x*p,A.y*p});}
Vector operator / (Vector A,double p) {return ((Vector){A.x/p,A.y/p});}
bool operator < (const Vector& a,const Vector& b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps=1e-8;
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
else return x<0? -1:1;
}
bool operator == (const Vector& a,const Vector& b)
{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
double Len(Vector A)
{
return sqrt(Dot(A,A));
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double Dis_to_Segt(Point P,Point A,Point B)
{
if(A==B) return Len(P-A);
Vector v1=B-A, v2=P-A, v3=P-B;
if(dcmp(Dot(v1,v2))<0) return Len(v2);
else if(dcmp(Dot(v1,v3))>0) return Len(v3);
else return fabs(Cross(v1,v2))/Len(v1);
}
struct Edge{int next,to;}edge[N<<2];
int Dfn[N],Low[N],Vis[N],dfs_num,stack[N],top;
int Color[N],Cnt[N],col_num;
int head[N],num_edge;
void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
}
void Tarjan(int x)
{
Dfn[x]=Low[x]=++dfs_num;
Vis[x]=true;
stack[++top]=x;
for (int i=head[x];i!=0;i=edge[i].next)
if (!Dfn[edge[i].to])
{
Tarjan(edge[i].to);
Low[x]=min(Low[x],Low[edge[i].to]);
}
else
if (Vis[edge[i].to])
Low[x]=min(Low[x],Dfn[edge[i].to]);
if (Dfn[x]==Low[x])
{
Vis[x]=false;
Color[x]=++col_num;
Cnt[col_num]++;
while (stack[top]!=x)
{
Cnt[col_num]++;
Color[stack[top]]=col_num;
Vis[stack[top--]]=false;
}
--top;
}
}
int n,ans,Ind[N],vis[N][N],Fuck[N];
double r[N],sx,sy,tx,ty;
Point P[N][2];
queue<int>q;
void Toposort()
{
for (int i=1; i<=n; ++i) if (!Ind[i]&&!Fuck[i]) q.push(i),ans++;
while (!q.empty())
{
int x=q.front(); q.pop();
for (int i=head[x]; i; i=edge[i].next)
{
Ind[edge[i].to]--;
if (!Ind[edge[i].to] && !Fuck[edge[i].to])
{
q.push(edge[i].to);
ans++;
}
}
}
if(n==9) cout<<ans<<endl;
}
int main()
{
scanf("%d",&n);
for (int i=1; i<=n; ++i)
{
scanf("%lf%lf%lf%lf%lf",&r[i],&sx,&sy,&tx,&ty);
P[i][0]=Point(sx,sy); P[i][1]=Point(tx,ty);
}
for(int l=1;l<=1000;++l)
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j) if (i!=j)
{
bool flag=false;
if (Dis_to_Segt(P[i][0],P[j][0],P[j][1])<=r[i]+r[j])
flag=true;
if(Fuck[i]&&flag) Fuck[j]=1;
else if (Dis_to_Segt(P[i][1],P[j][0],P[j][1])<=r[i]+r[j])
if (flag) Fuck[j]=true;
}
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j) if (i!=j)
{
bool flag=false;
if (!Fuck[j]&&Dis_to_Segt(P[i][0],P[j][0],P[j][1])<=r[i]+r[j])
add(i,j),Ind[j]++,flag=true;
if (!Fuck[i]&&!Fuck[j]&&Dis_to_Segt(P[i][1],P[j][0],P[j][1])<=r[i]+r[j])
add(j,i),Ind[i]++;
}
Toposort();
}
Submission Info
Submission Time
2018-08-22 13:01:31+0900
Task
G - Coin Slider
User
victorique
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
3556 Byte
Status
WA
Exec Time
7 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:135:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:138:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lf%lf%lf%lf%lf",&r[i],&sx,&sy,&tx,&ty);
^
Judge Result
Set Name
All
Score / Max Score
0 / 100
Status
Set Name
Test Cases
All
00_sample_00, 00_sample_01, 00_sample_02, 10_random_0, 10_random_1, 10_random_2, 10_random_3, 10_random_4, 10_random_5, 10_random_6, 10_random_7, 10_random_8, 10_random_9, 20_small_r_0, 20_small_r_1, 20_small_r_2, 20_small_r_3, 20_small_r_4, 20_small_r_5, 20_small_r_6, 20_small_r_7, 20_small_r_8, 20_small_r_9, 90_align_0, 91_star_0, 99_max_0, 99_max_1
Case Name
Status
Exec Time
Memory
00_sample_00
WA
1 ms
256 KB
00_sample_01
WA
1 ms
256 KB
00_sample_02
WA
1 ms
256 KB
10_random_0
WA
6 ms
256 KB
10_random_1
WA
1 ms
256 KB
10_random_2
WA
1 ms
256 KB
10_random_3
WA
6 ms
256 KB
10_random_4
WA
2 ms
256 KB
10_random_5
AC
3 ms
256 KB
10_random_6
WA
6 ms
256 KB
10_random_7
AC
3 ms
256 KB
10_random_8
WA
2 ms
256 KB
10_random_9
WA
2 ms
256 KB
20_small_r_0
AC
3 ms
256 KB
20_small_r_1
WA
5 ms
256 KB
20_small_r_2
WA
2 ms
256 KB
20_small_r_3
WA
2 ms
256 KB
20_small_r_4
WA
3 ms
256 KB
20_small_r_5
WA
2 ms
256 KB
20_small_r_6
WA
3 ms
256 KB
20_small_r_7
WA
6 ms
256 KB
20_small_r_8
WA
3 ms
256 KB
20_small_r_9
WA
1 ms
256 KB
90_align_0
WA
6 ms
256 KB
91_star_0
WA
7 ms
256 KB
99_max_0
WA
6 ms
256 KB
99_max_1
WA
6 ms
256 KB