我的电脑做网站服务器,百度关键词优化和百度推广,做游戏开发需要学哪些技术,wordpress怎么被百度收录B Convex Polygon
题意#xff1a;
有n个点#xff0c;每两个点组成一个坐标#xff0c;现在问你是否所有的点可以构成一个凸多边形。并且这些点应该以顺时针方向输出。
题解#xff1a;
很明显裸的凸包板子题#xff0c;但是我们队里没人负责计算几何#xff0c;当时…B Convex Polygon
题意
有n个点每两个点组成一个坐标现在问你是否所有的点可以构成一个凸多边形。并且这些点应该以顺时针方向输出。
题解
很明显裸的凸包板子题但是我们队里没人负责计算几何当时抄的kuangbin板子太啰嗦了以后应该自己整理 然后又调了半小时 也算是复习一下凸包了 我们以为判断全了结果忘了特判是不是所有点参与构成凸包而错失八题
代码
比赛代码
#includebits/stdc.h
using namespace std;
const int maxp1020;
const double eps1e-8;
const double piacos(-1.0);
typedef pairint,int pii;
#define x first
#define y second
#define double int
int sgn(double x){if(fabs(x)eps)return 0;if(x0)return -1;else return 1;
}
struct Point{double x,y;Point(){}Point(double _x,double _y){x_x;y_y;}bool operator(Point b)const{return sgn(x-b.x)0sgn(y-b.y)0;}bool operator(Point b)const{return sgn(x-b.x)0?sgn(y-b.y)0:xb.x;}Point operator(const Point b)const {return Point(xb.x,yb.y);}Point operator-(const Point b)const {return Point(x-b.x,y-b.y);}double operator^(const Point b)const {return x*b.y-y*b.x; }double distance(Point p){return hypot(x-p.x,y-p.y);}};
struct Line{Point s,e;Line(){}Line(Point _s,Point _e){s_s;e_e;}bool operator(Line v){return (sv.s)(ev.e);}Line(Point p,double angle){sp;if(sgn(angle-pi/2)0){e(sPoint(0,1));}else {e(sPoint(1,tan(angle)));}}Line(double a,double b,double c){if(sgn(a)0){sPoint(0,-c/b);ePoint(1,-c/b);}else if(sgn(b)0){sPoint(-c/a,0);ePoint(-c/a,1);}else {sPoint(0,-c/b);ePoint(1,(-c-a)/b);}}};
const int N110;
pii q[N];
int n;
struct polygon{int n;Point p[maxp];Line l[maxp];void input(int jcy){njcy;
// coutnendl;for(int i0;in;i){p[i]Point(q[i1].x*1.0,1.0*q[i1].y);
// coutp[i].x p[i].yendl;
// p[i].input();}}void getline(){for(int i0;in;i){l[i]Line(p[i],p[(i1)%n]);}} struct cmp{Point p;cmp(const Point p0){pp0;}bool operator()(const Point aa,const Point bb){Point aaa,bbb;int dsgn((a-p)^(b-p));if(d0){return sgn(a.distance(p)-b.distance(p))0;}return d0;}};void norm(){Point mip[0];for(int i1;in;i)mimin(mi,p[i]);sort(p,pn,cmp(mi));}void getconvex(polygon convex){sort(p,pn);convex.nn;
// for(int i0;in;i) coutp[i].x p[i].yendl;
// coutnendl;for(int i0;imin(n,2);i){convex.p[i]p[i];
// coutconvex.p[i].xendl;}if(convex.n2(convex.p[0]convex.p[1]))convex.n--;if(n2)return ;int topconvex.n;top1;for(int i2;in;i){while(topsgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))0){top--;}convex.p[top]p[i];}int temptop;convex.p[top]p[n-2];for(int in-3;i0;i--){while(top!tempsgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))0){top--;}convex.p[top]p[i];}if(convex.n2(convex.p[0]convex.p[1]))convex.n--;
// convex.norm();}
}P;pii get(int a,int b,int c,int d){int dyd-b;int dxc-a;int dd__gcd(dx,dy);dy/dd;dx/dd;if(dy0) dy*-1,dx*-1;return {dy,dx};
}
signed main (){int cnt0;int x,y;string s; cins;vectorintv;int res0;int tot0;for(int i0;is.size();i){if(s[i],){continue;}tot;int ji;int f1;while(js.size()s[j]!,){//1,1,1,3,-1,3if(s[j]-) f*-1;else{resres*10s[j]-0; }j;}ij-1;
// coutres*fendl;v.push_back(f*res);res0;}if(v.size()1){coutERROR;return 0;}int D1010;for(int i0;iv.size();i2){q[n]{v[i]D,v[i1]D};}if(n2){coutERROR;return 0;}for(int i1;in;i){for(int j1;jn;j){for(int k1;kn;k)if(i!j j!k i!k){if(get(q[i].x,q[i].y,q[j].x,q[j].y)get(q[j].x,q[j].y,q[k].x,q[k].y)){coutERROR;return 0;}}}}
// coutnendl;P.input(n);P.getline(); polygon tt;P.getconvex(tt);double dist1e18;int id0;
// couttt.nendl;if(tt.n!tot/2){coutERROR;return 0;}for(int i0;itt.n;i){tt.p[i].x-D;tt.p[i].y-D;
// couttt.p[i].x tt.p[i].yendl;if(tt.p[i].x*tt.p[i].xtt.p[i].y*tt.p[i].ydist){distmin(dist,tt.p[i].x*tt.p[i].xtt.p[i].y*tt.p[i].y);idi;}}vectorpiivv;
// coutidendl;bool flagfalse;for(int iid;itt.n;i){double xtt.p[i].x;double ytt.p[i].y;if(!flag)cout(int)x,(int)y,flagtrue;elsecout,(int)x,(int)y;}for(int i0;iid;i){double xtt.p[i].x;double ytt.p[i].y;if(!flag)cout(int)x,(int)y,flagtrue;elsecout,(int)x,(int)y;}
// for(int i0;ivv.size();i){
//
// coutvv[i].x,vv[i].y;
// if(i!vv.size()-1)
// cout,;if(i!(int)vv.size()-1)
//
// }
//
}赛后代码
#includebits/stdc.h
using namespace std;const double eps 1e-12;
#define Point pairdouble,double
#define x first
#define y secondint sign(double x)
{if(fabs(x) eps) return 0;return x0 ? -1:1;
}
Point operator-(Point a, Point b) {return {a.x-b.x, a.y-b.y};} // 向量
double cross(Point a, Point b) {return a.x * b.y - b.x * a.y;} // 叉积
double area(Point a, Point b, Point c) {return cross(b-a, c-a);} // 判向
double get_dis(Point a, Point b)
{double dx a.x - b.x;double dy a.y - b.y;return sqrt(dx * dx dy * dy);
}int n,top;
bool vis[110];
Point pt[10010];
int stk[10010];
void Graham()
{sort(pt1, pt1n);top 0;int ck;for(int i1;in;i){while(top1 (ck sign(area(pt[stk[top-1]], pt[stk[top]], pt[i]))) 0){vis[stk[top]] 0;top--;}stk[top] i;vis[i] 1;}vis[1] 0;for(int in;i1;i--){if(vis[i]) continue;while(top1 sign(area(pt[stk[top-1]], pt[stk[top]], pt[i])) 0)top--;stk[top] i;}if(stk[top]1) top--;
}
bool check()
{for(int i1;in;i){for(int ji1;jn;j){for(int kj1;kn;k){if(sign(area(pt[i], pt[j], pt[k])) 0)return 1;}}}return 0;
}
void solve()
{n 0;char c;double x,y;while(scanf(%lf,%lf,x, y)!EOF){pt[n] {x,y};scanf(%c,c);}if(check()){coutERRORendl;return ;}Graham();if(top!n)coutERRORendl;else{Point cc {0,0};int k 1;for(int i2;itop;i){if(get_dis(pt[stk[i]],cc) get_dis(pt[stk[k]],cc))k i;}for(int i1;itop;i){printf(%.0lf,%.0lf,pt[stk[k]].x, pt[stk[k]].y);if(i!top) printf(,);k--;if(k0) k top;}}
}
int main()
{freopen(data.in,r,stdin); solve();return 0;
}
