怎么做旅行网站,石家庄新闻发布会最新消息,学网站建设工作室,重庆电子工程职业学院教育网LA 4992 hdu 3761 Jungle Outpost 杭电的有点坑啊。。一直爆内存#xff0c;后来发现大白的半平面交模板那里 point *p new point[n]; line *q new line[n]这里出了问题#xff0c;应该是在函数里面申请不了比较大的数组#xff0c;所以爆内存。。我在全局定义…LA 4992 hdu 3761 Jungle Outpost 杭电的有点坑啊。。一直爆内存后来发现大白的半平面交模板那里 point *p new point[n]; line *q new line[n]这里出了问题应该是在函数里面申请不了比较大的数组所以爆内存。。我在全局定义了两个数组就不会爆了。。 本来跑了17s多的后来半平面交sort( l, l n ) 被我注释了就跑了9s多LA上跑了 2s。。应该是输入数据比较好不用按照极角排序。。然后就是照着大白的想法二分答案用半平面交判断是否满足条件。。 输入是按照逆时针输入的所以用p[i] - p[(im1)%n]表示直线的向量。。 这道题被坑了好久好伤心。。贴的是在杭电ac的代码 1 #includeiostream2 #includecstring3 #includecstdio4 #includestring5 #includealgorithm6 #includequeue7 #includecmath8 #includevector9 10 using namespace std;11 12 #define mnx 5005013 #define LL long long14 #define mod 100000000715 #define inf 0x3f3f3f3f16 #define eps 1e-817 #define Pi acos(-1.0);18 #define lson l, m, rt 119 #define rson m1, r, rt 1 | 120 21 int dcmp( double x ){22 if( fabs( x ) eps ) return 0;23 return x 0 ? -1 : 1;24 }25 struct point{26 double x, y;27 point( double x 0, double y 0 ) : x(x), y(y) {}28 point operator ( const point b ) const{29 return point( x b.x, y b.y );30 }31 point operator - ( const point b ) const{32 return point( x - b.x, y - b.y );33 }34 point operator * ( const double k ) const{35 return point( x * k, y * k );36 }37 point operator / ( const double k ) const{38 return point( x / k, y / k );39 }40 bool operator ( const point b ) const{41 return dcmp( x - b.x ) 0 || dcmp( x - b.x ) 0 dcmp( y - b.y ) 0;42 }43 bool operator ( const point b ) const{44 return dcmp( x - b.x ) 0 dcmp( y - b.y ) 0;45 }46 double len(){47 return sqrt( x * x y * y );48 }49 };50 typedef point Vector;51 struct line{52 point p; 53 Vector v;54 double ang;55 line() {}56 line( point p, point v ) : p(p), v(v) {57 ang atan2( v.y, v.x );58 }59 bool operator ( const line b ) const{60 return ang b.ang;61 }62 };63 double dot( Vector a, Vector b ){64 return a.x * b.x a.y * b.y;65 }66 double cross( Vector a, Vector b ){67 return a.x * b.y - a.y * b.x;68 }69 bool onleft( line l, point p ){70 return cross( l.v, p - l.p ) 0;71 }72 point getintersection( line a, line b ){73 Vector u a.p - b.p;74 double t cross( b.v, u ) / cross( a.v, b.v );75 return a.p a.v * t;76 }77 point pp[mnx];78 line q[mnx];79 int halfplaneintersection( line *L, int n, point *poly ){80 //sort( L, L n );81 int first, last;82 q[first last 0] L[0];83 for( int i 1; i n; i ){84 while( first last !onleft( L[i], pp[last-1] ) ) last--;85 while( first last !onleft( L[i], pp[first] ) ) first;86 q[last] L[i];87 if( fabs( cross( q[last].v, q[last-1].v ) ) eps ){88 last--;89 if( onleft( q[last], L[i].p ) ) q[last] L[i];90 }91 if( first last ) pp[last-1] getintersection( q[last-1], q[last] );92 }93 while( first last !onleft( q[first], pp[last-1] ) ) last--;94 if( last - first 1 ) return 0;95 pp[last] getintersection( q[last], q[first] );96 int m 0;97 for( int i first; i last; i ){98 poly[m] pp[i];99 }
100 return m;
101 }
102 point p[mnx], poly[mnx];
103 line l[mnx];
104 bool check( int n, int m ){
105 if( n - m 2 ) return 1;
106 for( int i 0; i n; i ){
107 l[i] line( p[i], p[i] - p[(im1)%n] );
108 }
109 int all halfplaneintersection( l, n, poly );
110 if( !all ) return 1;
111 else return 0;
112 }
113 int main(){
114 int n, cas;
115 scanf( %d, cas );
116 while( cas-- ){
117 scanf( %d, n );
118 for( int i 0; i n; i ){
119 scanf( %lf %lf, p[i].x, p[i].y );
120 }
121 if( n 50000 ) continue;
122 int l 0, r n, ans;
123 while( l r ){
124 int m ( l r ) 1;
125 if( check( n, m ) 1 ){
126 ans m, r m;
127 }
128 else l m 1;
129 }
130 printf( %d\n, ans );
131 }
132 return 0;
133 } View Code 转载于:https://www.cnblogs.com/LJ-blog/p/3960924.html
