题意：
- 给n个点，判断这个n个点是否能用不多于两条直线全覆盖
思路：
- 如果只有不到三个点，那么直接返回”YES“
- 否则，显然任意挑三个点，这三个点有两种情况
- 三个点重合，在一条直线上
显然这三个点需要用掉一条边，只需要查看剩下来的点能不能只在一条边上 - 三个点组成一个三角形，与上同理，至少用掉两条边来满足这个三角形的覆盖
所以判断三种可能是否还有剩余的的点未被覆盖，返回结果 - 用计算几何板子需要调整eps精度，开long double（因为点很大）
1 #include<bits/stdc++.h>
2 #define debug1(a) cout<<#a<<'='<< a << endl;
3 #define debug2(a,b) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<endl;
4 #define debug3(a,b,c) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<endl;
5 #define debug4(a,b,c,d) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<endl;
6 #define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<" "<<#e<<" = "<<e<<endl;
7 #define endl "\n"
8 #define fi first
9 #define se second
10
11 #define int long long
12 //#define double long double
13 //#define int __int128
14 using namespace std;
15
16 typedef long long LL;
17 typedef unsigned long long ULL;
18 typedef pair<int,int> PII;
19 typedef pair<LL,LL> PLL;
20
21 //#pragma GCC optimize(3,"Ofast","inline")
22 //#pragma GCC optimize(2)
23
24 //常数定义
25 const double eps = 1e-10;//根据需要调整
26 const double PI = acos(-1.0);
27 const int INF = 0x3f3f3f3f;
28 const int N = 1e5+10;
29 int sgn(double x)//符号函数，eps使用最多的地方
30 {
31 if (fabs(x) < eps)
32 return 0;
33 if (x < 0)
34 return -1;
35 else
36 return 1;
37 }
38
39 //点类及其相关操作
40 struct Point
41 {
42 double x, y;
43 Point() {}
44 Point(double _x, double _y) : x(_x), y(_y) {}
45 Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
46 Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
47
48 double operator^(const Point &b) const { return x * b.y - y * b.x; } //叉积
49 double operator*(const Point &b) const { return x * b.x + y * b.y; } //点积
50
51 bool operator<(const Point &b) const { return x < b.x || (x == b.x && y < b.y); }
52 bool operator==(const Point &b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; }
53
54 Point Rotate(double B, Point P) //绕着点P，逆时针旋转角度B(弧度)
55 {
56 Point tmp;
57 tmp.x = (x - P.x) * cos(B) - (y - P.y) * sin(B) + P.x;
58 tmp.y = (x - P.x) * sin(B) + (y - P.y) * cos(B) + P.y;
59 return tmp;
60 }
61 };
62
63 double dist(Point a, Point b) { return sqrt((a - b) * (a - b)); } //两点间距离
64 double len(Point a){return sqrt(a.x * a.x + a.y * a.y);}//向量的长度
65
66 struct Line
67 {
68 Point s, e;
69 Line() {}
70 Line(Point _s, Point _e) : s(_s), e(_e) {}
71
72 //两直线相交求交点
73 //第一个值为0表示直线重合，为1表示平行,为2是相交
74 //只有第一个值为2时，交点才有意义
75
76 pair<int, Point> operator&(const Line &b) const
77 {
78 Point res = s;
79 if (sgn((s - e) ^ (b.s - b.e)) == 0)
80 {
81 if (sgn((s - b.e) ^ (b.s - b.e)) == 0)
82 return make_pair(0, res); //重合
83 else
84 return make_pair(1, res); //平行
85 }
86 double t = ((s - b.s) ^ (b.s - b.e)) / ((s - e) ^ (b.s - b.e));
87 res.x += (e.x - s.x) * t;
88 res.y += (e.y - s.y) * t;
89 return make_pair(2, res);
90 }
91 };
92
93 //*判断点在直线上的垂点
94 Point PointToLine(Point P, Line L)
95 {
96 Point result;
97 double t = ((P - L.s) * (L.e - L.s)) / ((L.e - L.s) * (L.e - L.s));
98 result.x = L.s.x + (L.e.x - L.s.x) * t;
99 result.y = L.s.y + (L.e.y - L.s.y) * t;
100 return result;
101 }
102
103 bool used[N];
104 Point points[N];
105 int n;
106 bool check(Line a)
107 {
108 //debug1((PointToLine(points[4],a) == points[4]));
109 memset(used, 0, sizeof(used));
110
111 for(int i = 0;i < n;i ++)
112 {
113 if(PointToLine(points[i],a) == points[i])used[i] = 1;
114 else used[i] = 0;
115 }
116
117 int cnt = 0;
118 Point t1,t2;
119
120 for(int i = 0;i < n;i ++)if(!used[i])
121 {
122 //debug2("re",i);
123 cnt ++;
124 if(cnt == 2)
125 {
126 t2 = points[i];
127 break;
128 }
129 t1 = points[i];
130 }
131
132
133 if(cnt < 2)return 1;
134 else{
135 Line remainder_line(t1,t2);
136 for(int i = 0;i < n;i ++)if(!used[i])
137 {
138 if(PointToLine(points[i],remainder_line) == points[i]) used[i] = 1;
139 else return 0;
140 }
141 }
142 return 1;
143 }
144
145 void solve()
146 {
147 cin >> n;
148 for(int i = 0;i < n;i ++)
149 {
150 int x,y;cin >> x;cin >> y;
151 points[i].x = x; points[i].y = y;
152 //debug2(points[i].x,points[i].y);
153 }
154
155 if(n <= 3)
156 {
157 cout << "YES" << endl;
158 return ;
159 }
160
161 Line l0(points[0],points[1]);
162 Line l1(points[1],points[2]);
163 Line l2(points[0],points[2]);
164
165 if(check(l0) || check(l1) || check(l2))
166 {
167 cout << "YES" << endl;
168 }else{
169 cout << "NO" << endl;
170 }
171
172 }
173
174 signed main()
175 {
176
177 /*
178 ios::sync_with_stdio(false);
179 cin.tie(0);
180 cout.tie(0);
181 */
182 int T = 1;//cin >> T;
183
184 while(T--){
185 //puts(solve()?"YES":"NO");
186 solve();
187 }
188 return 0;
189
190 }
191 /*
192
193 */
标签：思维,const,Point,int,double,Lines,points,Pair,return From： https://www.cnblogs.com/cfddfc/p/17067363.html