Submission #2464982
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long Int64;
const double pi = acos(-1.0);
const double eps = 1e-5;
const int INF = 1000000000;
const int maxn =100;
int n,m,T;
int cmp(double x){
return fabs(x)<eps?0:(x>0?1:-1);
}
inline int sqr(int x){
return x*x;
}
struct point{
int x,y;
point(int a=0,int b=0):x(a),y(b){}
friend point operator -(const point &a,const point &b){
return point(a.x-b.x,a.y-b.y);
}
double norm(){
return sqrt(sqr(x)+sqr(y));
}
};
double det(const point &a,const point &b ){
return a.x*b.y-a.y*b.x;
}
double dot(const point &a,const point &b ){
return a.x*b.x+a.y*b.y;
}
double dist(const point &a,const point &b ){
return (a-b).norm();
}
double dis_point_segment(const point p,const point s,const point t){
if(cmp(dot(p-s,t-s))<0)return (p-s).norm();
if(cmp(dot(p-t,s-t))<0)return (p-t).norm();
return fabs(det(s-p,t-p)/dist(s,t));
}
int round1[maxn];
point p[maxn*2];
bool record[maxn][maxn*2];
bool dp[1<<20];
int count1(int n){
int ans=0;
while(n){
ans+=n%2;
n/=2;
}
return ans;
}
int main()
{
memset(record,0,sizeof(record));
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d%d%d",&round1[i],&p[2*i].x,&p[2*i].y,&p[2*i+1].x,&p[2*i+1].y);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
if(dis_point_segment(p[2*j],p[2*i],p[2*i+1])+eps<round1[i]+round1[j])record[i][2*j]=true;//i移动会碰到j的起点
if(dis_point_segment(p[2*j+1],p[2*i],p[2*i+1])+eps<round1[i]+round1[j])record[i][2*j+1]=true;//i移动会碰到j的终点
}
}
dp[0]=true;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(((i>>j)&1)==0){//当前j位为0
bool flag=false;
for(int k=0;k<n;k++){
if(k==j)continue;
int ip=(i>>k)&1;
if(ip==1&&record[j][2*k+1])flag=true;
if(ip==0&&record[j][2*k])flag=true;
}
if(!flag&&dp[i]){
dp[i|1<<j]=true;
}
}
}
}
int ans=0;
for(int i=0;i<(1<<n);i++){
if(dp[i])
ans=max(ans,count1(i));
}
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time
2018-05-05 21:42:45+0900
Task
G - Coin Slider
User
yuxudong1512025
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2489 Byte
Status
AC
Exec Time
37 ms
Memory
1280 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:65:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:68:83: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d",&round1[i],&p[2*i].x,&p[2*i].y,&p[2*i+1].x,&p[2*i+1].y);
^
Judge Result
Set Name
All
Score / Max Score
100 / 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
AC
2 ms
1280 KB
00_sample_01
AC
2 ms
1280 KB
00_sample_02
AC
2 ms
1280 KB
10_random_0
AC
35 ms
1280 KB
10_random_1
AC
2 ms
1280 KB
10_random_2
AC
2 ms
1280 KB
10_random_3
AC
17 ms
1280 KB
10_random_4
AC
2 ms
1280 KB
10_random_5
AC
2 ms
1280 KB
10_random_6
AC
17 ms
1280 KB
10_random_7
AC
2 ms
1280 KB
10_random_8
AC
2 ms
1280 KB
10_random_9
AC
2 ms
1280 KB
20_small_r_0
AC
2 ms
1280 KB
20_small_r_1
AC
9 ms
1280 KB
20_small_r_2
AC
2 ms
1280 KB
20_small_r_3
AC
2 ms
1280 KB
20_small_r_4
AC
2 ms
1280 KB
20_small_r_5
AC
2 ms
1280 KB
20_small_r_6
AC
2 ms
1280 KB
20_small_r_7
AC
17 ms
1280 KB
20_small_r_8
AC
2 ms
1280 KB
20_small_r_9
AC
2 ms
1280 KB
90_align_0
AC
35 ms
1280 KB
91_star_0
AC
35 ms
1280 KB
99_max_0
AC
37 ms
1280 KB
99_max_1
AC
36 ms
1280 KB