P1355 神秘大三角（凸包）

P1355 神秘大三角 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

队友推荐的，算是入门凸包，就是用叉积判断一下点是否相对每条边都在凸包的边的左侧。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace  std;
  4 
  5 #define ll long long
  6 
  7 const int N=1e3+10;
  8 
  9 double eps=1e-8;
 10 
 11 double pi=acos(-1);
 12 
 13 struct Point{
 14 
 15     double x,y;
 16 
 17     Point(double x=0,double y=0):x(x),y(y){};
 18 
 19 };
 20 
 21 typedef Point Vector;
 22 
 23 Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
 24 
 25 Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
 26 
 27 Vector operator *(Vector A,double B){return Vector(A.x*B,A.y*B);}
 28 
 29 Vector operator /(Vector A,double B){return Vector(A.x/B,A.y/B);}
 30 
 31 int dcmp(double x){
 32 
 33     if(fabs(x)<eps)return 0;
 34 
 35     return x<0?-1:1;
 36 
 37 }
 38 
 39 bool operator<(const Point&a,const Point&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
 40 
 41 bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
 42 
 43 double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
 44 
 45 double Length(Vector A){return sqrt(Dot(A,A));}
 46 
 47 double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
 48 
 49 double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}
 50 
 51 double Angle(Vector A) {return atan2(A.y, A.x);}
 52 
 53  
 54 
 55 struct Circle{    //圆
 56 
 57     Point c;
 58 
 59     double r;
 60 
 61     Circle(Point c = Point(0, 0), double r = 0):c(c),r(r){}
 62 
 63     Point point(double a){
 64 
 65         return Point(c.x+cos(a)*r,c.y+sin(a)*r);
 66 
 67     }
 68 
 69 };
 70 
 71 double dis(Point A,Point B){
 72 
 73     return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
 74 
 75 }
 76 
 77 int circle_circle(Circle C1,Circle C2,vector<Point>&sol){//返回圆与圆的交点个数
 78 
 79     double d=Length(C1.c-C2.c);
 80 
 81     if(dcmp(d)==0){
 82 
 83         if(dcmp(C1.r-C2.r)==0)return -1;
 84 
 85         return 0;
 86 
 87     }
 88 
 89     if(dcmp(C1.r+C2.r-d)<0)return 0;
 90 
 91     if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;
 92 
 93     double a=Angle(C2.c-C1.c);
 94 
 95     double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*d*C1.r));
 96 
 97     Point p1=C1.point(a-da),p2=C1.point(a+da);
 98 
 99     sol.push_back(p1);
100 
101     if(p1==p2)return 1;
102 
103     sol.push_back(p2);
104 
105     return 2;
106 
107 }
108 
109  
110 
111 Point line_point(Point p,Vector v,Point q,Vector w){//直线交点
112 
113     Vector u=p-q;
114 
115     double t=Cross(w,u)/Cross(v,w);
116 
117     return p+v*t;
118 
119 }
120 
121 bool onsegment(Point p,Point a1,Point a2){
122 
123     if(p==a1||p==a2)return true;
124 
125     return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
126 
127 }
128 
129 bool segmentcross(Point a1,Point a2,Point b1,Point b2){
130 
131     double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
132 
133            c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
134 
135     return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
136 
137 }
138 
139 Point line_line(Point A,Point B,Point C,Vector D){//线段交点
140 
141     if(segmentcross(A,B,C,D)){
142 
143         return line_point(A,B-A,C,D-C);
144 
145     }
146 
147     return Point(123.456,0);
148 
149 }
150 
151 int tubao(Point *p,int n,Point *ch){
152 
153     sort(p,p+n);
154 
155     n=unique(p,p+n)-p;
156 
157     int m=0;
158 
159     for(int i=0;i<n;i++){
160 
161         while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
162 
163         ch[m++]=p[i];
164 
165     }
166 
167     int k=m;
168 
169     for(int i=n-2;i>=0;i--){
170 
171         while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
172 
173         ch[m++]=p[i];
174 
175     }
176 
177     if(n>1)m--;
178 
179     return m;
180 
181 }
182 
183 double tubaos(Point *p,int n){
184 
185     double area=0;
186 
187     for(int i=1;i<n-1;i++){
188 
189         area+=Cross(p[i]-p[0],p[i+1]-p[0]);
190 
191     }
192 
193     return area/2;
194 
195 }
196 
197 int intubao(Point *ch,int n,Point p){
198 
199     Vector A,B;
200 
201     int flag=0;
202 
203     for(int i=0;i<n;i++){
204         if(ch[i] == p)return -2; //p在凸包端点上
205 
206         A=ch[(i+1)%n]-ch[i];
207 
208         B=p-ch[i];
209 
210         if(onsegment(p,ch[i],ch[(i+1)%n])){
211 
212             flag=-1;//在凸包边上
213 
214             break;
215 
216         }
217 
218         else if(Cross(A,B)>0){
219 
220             flag++;
221 
222         }
223 
224     }
225 
226     if(flag==-1||flag==n)return flag;//flag=n说明在凸包里面
227 
228     return 0;//在凸包外面
229 
230 }
231 
232 double x[N],y[N];
233 
234 Point p[N],q[N],ch[N],ans[N];
235 
236 int main(){
237 
238     char c;
239 
240     for(int i = 0;i < 4;i++){
241         cin >> c >> p[i].x >> c >> p[i].y >> c;
242     }
243     
244     int n = tubao(p, 3, ch);
245     int res = intubao(ch, n, p[3]);
246     if(res == 3)cout << 1 << endl;
247     else if(res == 0)cout << 2 << endl;
248     else if(res == -1)cout << 3 << endl;
249     else cout << 4 << endl;
250 
251 
252 }