Submission #2457979

---

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];
int dp[1<<20];



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的终点
        }
    }
    //cout<<(1<<n)<<endl;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            //cout<<i<<" "<<j<<endl;
            if(((i>>j)&1)==0){//当前j位为0
                //cout<<((i>>j)&1)<<endl;
                bool flag=false;
                for(int k=0;k<n;k++){
                    if(k==j)continue;
                    int ip=(i>>k)&1;
                    //cout<<ip<<endl;
                    if(ip==1&&record[j][2*k+1])flag=true;
                    if(ip==0&&record[j][2*k])flag=true;
                }
                if(!flag){
                    dp[i|1<<j]=max(dp[i|1<<j],dp[i]+1);
                }
                else
                    dp[i|1<<j]=max(dp[i|1<<j],dp[i]);
            }

        }
    }
    int ans=0;
    for(int i=0;i<(1<<n);i++)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:61: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