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
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
AC × 27
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