#37294 (C++11) No.245 貫け！

提出ソース
結果

問題	No.245 貫け！
ユーザー	LayCurse
提出日時	2015-07-17 23:06:49
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	136 ms / 5,000 ms
コード長	14,033 bytes
コンパイル時間	1,686 ms
コンパイル使用メモリ	152,472 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-22 18:08:34
合計ジャッジ時間	3,362 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	9 ms 4,380 KB
testcase_10	AC	13 ms 4,376 KB
testcase_11	AC	49 ms 4,380 KB
testcase_12	AC	132 ms 4,376 KB
testcase_13	AC	132 ms 4,380 KB
testcase_14	AC	129 ms 4,376 KB
testcase_15	AC	132 ms 4,376 KB
testcase_16	AC	134 ms 4,376 KB
testcase_17	AC	133 ms 4,380 KB
testcase_18	AC	136 ms 4,376 KB
testcase_19	AC	136 ms 4,380 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

char memarr[17000000]; void *mem = memarr;
#define MD 1000000007


#define EPS 1e-10
#define PI 3.141592653589793238462
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
typedef struct struct_point{double x,y;}pnt;
typedef struct struct_line{pnt a,b;}line;
typedef struct struct_circle{pnt c; double r;}circle;

int doubleSign(double a){if(a>EPS) return 1; if(a<-EPS) return -1; return 0;}
int doubleSignR(double a,double b){ if(doubleSign(b)!=0 && doubleSign(a/b-1)==0) return 0; return doubleSign(a-b);}
int pntSign(pnt a){int i=doubleSign(a.x); if(i) return i; return doubleSign(a.y);}

pnt pntPlus(pnt a,pnt b){a.x+=b.x; a.y+=b.y; return a;}
pnt pntMinus(pnt a,pnt b){a.x-=b.x; a.y-=b.y; return a;}
pnt pntMultiple(pnt a,pnt b){pnt c; c.x=a.x*b.x-a.y*b.y; c.y=a.x*b.y+a.y*b.x; return c;}
pnt pntMultipleDouble(pnt a,double k){a.x*=k; a.y*=k; return a;}

int pntIsEqual(pnt a,pnt b){return pntSign(pntMinus(a,b))==0;}

double pntLength(pnt a){return sqrt(a.x*a.x+a.y*a.y);}
double pntLength2(pnt a){return a.x*a.x+a.y*a.y;}
double pntDistance(pnt a,pnt b){return pntLength(pntMinus(a,b));}
double pntDistance2(pnt a,pnt b){return pntLength2(pntMinus(a,b));}
double pntArgument(pnt a){return atan2(a.y,a.x);}

pnt pntNormalize(pnt a){double n=pntLength(a); a.x/=n; a.y/=n; return a;}
double pntInnerProduct(pnt a,pnt b){return a.x*b.x+a.y*b.y;}
double pntOuterProduct(pnt a,pnt b){return a.x*b.y-a.y*b.x;}

pnt pntGenerator(double x,double y){pnt res; res.x=x; res.y=y; return res;}
line pntToLine(pnt a,pnt b){line res; res.a=a; res.b=b; return res;}
circle pntToCircle(pnt c,double r){circle res; res.c=c; res.r=r; return res;}

int isPntInCircle(pnt p,circle c){return doubleSign(c.r-pntDistance(p,c.c))+1;}
int isPntOnCircle(pnt p,circle c){if(doubleSign(pntDistance(p,c.c)-c.r)==0) return 1; return 0;}

/* aがbの厳密に内部なら2 */
int isCircleInCircle(circle a,circle b){return doubleSign(b.r-a.r-pntDistance(a.c,b.c))+1;}

pnt pntPolar(double r,double t){pnt a; a.x=r*cos(t); a.y=r*sin(t); return a;}
void pntSort(pnt d[],int s){int i,j;pnt k,t;if(s<=1)return;k=pntMultipleDouble(pntPlus(d[0],d[s-1]),1/2.0);i=-1;j=s;for(;;){while(pntSign(pntMinus(d[++i],k))==-1);while(pntSign(pntMinus(d[--j],k))==1);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}pntSort(d,i);pntSort(d+j+1,s-j-1);}

/* 点oのまわりに点aをtだけ回転した点を返す */
pnt pntRatation(pnt a,pnt o,double t){
  return pntPlus(pntMultiple(pntMinus(a,o),pntPolar(1.0,t)),o);
}

pnt pntRatationEasy(pnt a,double t){
  return pntMultiple(a,pntPolar(1.0,t));
}

/* 直線の上に載っていると1, 載ってなければ0 */
int isPntOnLine(pnt a,line s){
  pnt ab; double r;
  ab=pntMinus(s.b,s.a); r=pntDistance(s.a,a)/pntDistance(s.a,s.b);
  if( !pntIsEqual(a,pntPlus(s.a,pntMultipleDouble(ab,r)) ) && !pntIsEqual(a,pntMinus(s.a,pntMultipleDouble(ab,r)) ) ) return 0;
  return 1;
}

/* 線分の上に載っていると2, 端点なら1, 載ってなければ0 */
int isPntOnSegment(pnt a,line s){
  pnt ab; double r;
  ab=pntMinus(s.b,s.a); r=pntDistance(s.a,a)/pntDistance(s.a,s.b);
  if( !pntIsEqual(a,pntPlus(s.a,pntMultipleDouble(ab,r)) ) ) return 0;
  if( doubleSign(r)==-1 || doubleSign(r-1)==1 ) return 0;
  if( doubleSign(r)==0  || doubleSign(r-1)==0 ) return 1;
  return 2;
}


/* 角度bacを返す */
double angleOfTriangle(pnt a,pnt b,pnt c){
  double inner,n1,n2;
  inner=pntInnerProduct(pntMinus(b,a),pntMinus(c,a));
  n1=pntDistance(a,b); n2=pntDistance(a,c);
  inner=inner/n1/n2;
  if(inner>1) inner=1; if(inner<-1) inner=-1;
  return acos(inner);
}




/* 原点中心半径rの円に，pから接線を引いて，接線と円の交点を2つ求める */
/* 制約: pは円の外 */
void pntPointToCircleTangentialEasy(pnt p,double r,pnt *res1,pnt *res2){
  double a,b,c,d;
  if( doubleSign(p.x)==0 ){
    a=p.x; p.x=p.y; p.y=a;
    pntPointToCircleTangentialEasy(p,r,res1,res2);
    a=res1->x; res1->x=res1->y; res1->y=a;
    a=res2->x; res2->x=res2->y; res2->y=a;
    return;
  }
  a = pntLength2(p);
  b = -2*r*r*p.y;
  c = r*r*(r*r-p.x*p.x);
  d = sqrt(b*b-4*a*c);
  res1->y = (-b+d)/(2*a);
  res2->y = (-b-d)/(2*a);
  res1->x = (r*r-res1->y*p.y)/p.x;
  res2->x = (r*r-res2->y*p.y)/p.x;
}

/* 円cに，pから接線を引いて，接線と円の交点を2つ求める */
/* 制約: pは円の外 */
void pntPointToCircleTangential(pnt p,circle c,pnt *res1,pnt *res2){
  pntPointToCircleTangentialEasy( pntMinus(p,c.c), c.r, res1, res2 );
  *res1 = pntPlus(*res1,c.c);
  *res2 = pntPlus(*res2,c.c);
}







/* 点p から 直線t へ引いた垂線の足を返す */
pnt pntPointLinePerpendicular(pnt p,line t){
  double k; pnt ab,ap;
  ab=pntMinus(t.b, t.a);  ap=pntMinus(p, t.a);
  k=pntInnerProduct(ab,ap)/pntLength2(ab);
  return pntPlus( t.a, pntMultipleDouble(ab,k) );
}

/* 点p の 直線t に対して対称な点を求める */
pnt pntSymmetricPointWithLine(pnt p,line t){
  pnt go = pntPointLinePerpendicular(p,t);
  go=pntMinus(go,p); return pntPlus( p,pntMultipleDouble(go,2) );
}

double distancePntSegment(pnt p,line t){
  double d1,d2;
  pnt c = pntPointLinePerpendicular(p,t);
  if( isPntOnSegment(c,t) ) return pntDistance(p,c);
  d1 = pntDistance(p,t.a); d2 = pntDistance(p,t.b);
  if(d1 > d2) return d2; return d1;
}

double distancePntLine(pnt p,line t){
  return pntDistance(p,pntPointLinePerpendicular(p,t));
}




/* 速度vで動く点が直線に辿り着くまでの時間 (マイナスもあり) */
/* 戻り値 0=辿り着かない， 1=辿り着く, 2=恒にその直線上を動く */
/* return 1; のとき double res = 辿り着く時間 pnt reachPoint = 辿り着いた場所 */
int getTimeMovingPntReachLine(pnt p,pnt v,line s,double *res, pnt *reachPoint){
  pnt lineVector = pntNormalize(pntMinus(s.b,s.a));
  double inner = pntInnerProduct(lineVector,v);
  double dist  = distancePntLine(p,s);
  pnt vv = pntMinus(v,pntMultipleDouble(lineVector,inner));

  if(pntSign(vv)==0){
    if(doubleSign(dist)==0) return 2;
    return 0;
  }

  *res = dist / pntLength(vv);
  *reachPoint = pntPlus(p,pntMultipleDouble(v,*res));
  if( !isPntOnLine(*reachPoint, s) ){
    (*res) *= -1;
    *reachPoint = pntPlus(p,pntMultipleDouble(v,*res));
  }
  return 1;
}




/* 長さap : bp = s : tを満たす点pの集合(円)を返す 制約: s!=t */
circle pntSetDivisionPoint(pnt a,double s,pnt b,double t){
  pnt r1,r2,ab; circle res;
  ab=pntMinus(b,a);
  r1 = pntPlus(a,pntMultipleDouble(ab,s/(s+t)));
  r2 = pntPlus(a,pntMultipleDouble(ab,s/(s-t)));
  res.c = pntMultipleDouble(pntPlus(r1,r2),0.5); res.r=pntDistance(r1,r2)/2;
  return res;
}




/* a x^2 + b x + c = 0 を解く．戻り値は解の数．解の数が2ならres1 < res2． */
/* 解の数が無限なら return 3; */
int doubleSolveSecondDegreeEquation(double a,double b,double c,double *res1,double *res2){
  if(doubleSign(a)){
    double d=b*b-4*a*c; int m=doubleSign(d)+1;
    if(m==1) *res1=-b/(2*a);
    if(m==2){d=sqrt(d); *res1=(-b-d)/(2*a); *res2=(-b+d)/(2*a);}
    return m;
  }
  if(doubleSign(b)){*res1 = -b/c; return 1;}
  if(doubleSign(c)) return 0; return 3;
}

/* 直線 t と円 s の交点を求める．戻り値は交点の数．(3次元での球-直線の交点とほぼ同じコード) */
/* 2点で交わるなら，res1はt.aに近い側，res2はt.bに近い側 */
int pntIntersectionLineCircle(line t,circle s,pnt *res1,pnt *res2){
  int m; double a,b,c,t1,t2,k1,k2; pnt ab=pntMinus(t.b, t.a);
  a=b=0; c=-s.r*s.r;
  t1=t.a.x-s.c.x; t2=t.b.x-t.a.x; a+=t2*t2; b+=2*t1*t2; c+=t1*t1;
  t1=t.a.y-s.c.y; t2=t.b.y-t.a.y; a+=t2*t2; b+=2*t1*t2; c+=t1*t1;
  m=doubleSolveSecondDegreeEquation(a,b,c,&k1,&k2);
  if(m>=1) *res1 = pntPlus( t.a, pntMultipleDouble(ab,k1) );
  if(m>=2) *res2 = pntPlus( t.a, pntMultipleDouble(ab,k2) );
  return m;
}

/* 線分 t (端は含む) と円 s の交点を求める．戻り値は交点の数．(3次元での球-直線の交点とほぼ同じコード) */
/* 2点で交わるなら，res1はt.aに近い側，res2はt.bに近い側 */
int pntIntersectionSegmentCircle(line t,circle s,pnt *res1,pnt *res2){
  int m; double a,b,c,t1,t2,k1,k2; pnt ab=pntMinus(t.b, t.a);
  a=b=0; c=-s.r*s.r;
  t1=t.a.x-s.c.x; t2=t.b.x-t.a.x; a+=t2*t2; b+=2*t1*t2; c+=t1*t1;
  t1=t.a.y-s.c.y; t2=t.b.y-t.a.y; a+=t2*t2; b+=2*t1*t2; c+=t1*t1;
  m=doubleSolveSecondDegreeEquation(a,b,c,&k1,&k2);
  if(m>=2) if(doubleSign(k2)==-1 || doubleSign(k2-1)==1) m--;
  if(m>=1) if(doubleSign(k1)==-1 || doubleSign(k1-1)==1) k1=k2, m--;
  if(m>=1) *res1 = pntPlus( t.a, pntMultipleDouble(ab,k1) );
  if(m>=2) *res2 = pntPlus( t.a, pntMultipleDouble(ab,k2) );
  return m;
}

/* ax + by + c = 0 を表す直線を返す (制約: a=b=0ではない) */
line pntGetLineFromCoefficient(double a,double b,double c){
  line res;
  if( doubleSign(a)==0 ){
    res.a.x = 0; res.b.x = 1;
    res.a.y = res.b.y = -c/b;
  } else {
    res.a.y=0; res.b.y=1;
    res.a.x=-c/a; res.b.x=(-b-c)/a;
  }
  return res;
}

/* 2つの円の交点を求める．戻り値の値は交点の数．戻り値が3ならば無限点で交わる */
int pntIntersectionCircleCircle(circle s1,circle s2,pnt *res1,pnt *res2){
  double a,b,c; line t;
  double x1=s1.c.x, x2=s2.c.x, y1=s1.c.y, y2=s2.c.y, r1=s1.r, r2=s2.r;
  if( pntIsEqual(s1.c,s2.c) ){ if( doubleSign(s1.r-s2.r)==0 ) return 3; return 0; }
  a = 2*(x1-x2); b = 2*(y1-y2);
  c = (x2*x2-x1*x1) + (y2*y2-y1*y1) - (r2*r2-r1*r1);
  t = pntGetLineFromCoefficient(a,b,c);
  return pntIntersectionLineCircle(t,s1,res1,res2);
}

/* 三角形の符号付面積の2倍 */
double pntAreaOfTriangle2(pnt p1,pnt p2,pnt p3){
  double x1,x2,y1,y2;
  x1=p2.x-p1.x; x2=p3.x-p1.x;
  y1=p2.y-p1.y; y2=p3.y-p1.y;
  return x1*y2-x2*y1;
}

/* 符号付面積の符号を返す                   */
/* p1,p2の直線の左にp3がある場合，戻り値=1  */
/* p1,p2の直線の右にp3がある場合，戻り値=-1 */
/* p1,p2,p3が一直線上にある場合， 戻り値=0  */
int pntSignAreaOfTriangle(pnt p1,pnt p2,pnt p3){
  return doubleSign( pntAreaOfTriangle2(p1,p2,p3) );
}





/* 2直線の交点を求める (交わる点が無限大の場合の判定は未実装) */
/* 戻り値: 交点の数 無限大の場合も0を返す                     */
/* 後の仕様予定: return 2が無限大の場合                       */
int pntIntersectionLineLine(line s,line t,pnt *res){
  pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b;
  double r = (p4.y-p3.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p4.x-p3.x);
  if( doubleSign(r)==0 ) return 0;
  res->x = (p3.x*p4.y-p3.y*p4.x)*(p2.x-p1.x)-(p1.x*p2.y-p1.y*p2.x)*(p4.x-p3.x);
  res->y = (p3.y*p4.x-p3.x*p4.y)*(p2.y-p1.y)-(p1.y*p2.x-p1.x*p2.y)*(p4.y-p3.y);
  res->x /= r; res->y /= -r; return 1;
}

/* s=line, t=segment */
int pntIntersectionLineSegment(line s,line t,pnt *res){
  pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b;
  if(pntSignAreaOfTriangle(s.a, s.b, t.a)==0 || pntSignAreaOfTriangle(s.a, s.b, t.b)==0){
    return 1;
  }
  
  double x1,x2,y1,y2;
  if(pntIntersectionLineLine(s,t,res)!=1) return 0;
  x1=MIN(p3.x,p4.x)-EPS; x2=MAX(p3.x,p4.x)+EPS;
  y1=MIN(p3.y,p4.y)-EPS; y2=MAX(p3.y,p4.y)+EPS;
  if(res->x < x1 || x2 < res->x || res->y < y1 || y2 < res->y) return 0;
  if(pntIsEqual(*res,p3)) return 1;
  if(pntIsEqual(*res,p4)) return 1;
  return 2;
}


int N;
line p[100], s;
pnt ptmp;

int main(){
  int i, j, k;
  int res, tmp;

  reader(&N);
  rep(i,N) reader(&p[i].a.x, &p[i].a.y, &p[i].b.x, &p[i].b.y);

  res = min(2, N);

  rep(i,2*N) rep(j,2*N){
    tmp = 0;
    if(i<N) s.a = p[i].a; else s.a = p[i-N].b;
    if(j<N) s.b = p[j].a; else s.b = p[j-N].b;
    if(pntIsEqual(s.a,s.b)) continue;
    rep(k,N) if(pntIntersectionLineSegment(s,p[k],&ptmp)) tmp++;
    res = max(res, tmp);
  }

  writerLn(res);

  return 0;
}
yukicoder

結果

テストケース

ソースコード
