链接：https://ac.nowcoder.com/acm/contest/2908/F
来源：牛客网
题目描述
沉迷《原初幻想41》的冒险者Antinomy穿越到了第一世界，这是暗之战士一切开始的地方——水晶都/クリスタリウム/The Crystarium
见完水晶公后，Antinomy逛了逛，发现水晶都的防护罩由好几个魔法装置维持着，这些点由一条路通向水晶都的二层，在地图上看非常规整，于是他突发奇想：
假设在地图上有nnn个装置，第iii个（从111开始）装置的坐标是(i,yi)(i,y_i)(i,yi)，是否可以找出两条平行的直线，让这nnn个装置中的每一个都恰好在两条直线的其中一条上？要求每条直线至少经过一个装置。每个装置可看做一个点。
找出这两条这样的直线的话就可以修路，使得在食罪灵来袭时以最快的速度支援。你能计算出来吗？
输入描述:
第一行为一个数字nnn表示装置个数
第二行为nnn个空格分隔的整数表示y1,y2,y3,…,yny_1,y_2,y_3,…,y_ny1,y2,y3,…,yn
输出描述:
如果能够找到那么输出QWQ，否则输出QAQ
题目描述不多赘述了，网上好几个假算法的题解，服了
这个题目直接暴力即可，但是需要注意可能一个点孤立其余点共线，只需要特判一下你选出来的那个点孤立的时候可行与否即可，可行还需要和后面的其余点不共线（斜率不同）
代码很详细，自己领会吧
#include
using namespace std;
#define FAST_READ
#define DEBUG puts("------------")
typedef struct Point {
int x, y;
Point() {
}
Point(int x, int y) {
this->x = x;
this->y = y;
}
} po;
double calculate(po a, po b) {
//计算两点斜率
return (double)(a.y - b.y) / (double)(a.x - b.x);
}
vector arr;
int n;
int main()
{
#ifdef DEBUG
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
#endif // FAST_READ
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> y;
x = i;
arr.push_back(po(x, y));
}
if (arr.size() <= 4) {
//点数小于等于4个一定满足条件
puts("QWQ");
}
else {
int len = arr.size();
//两种情况
//1.第一个点孤立，其余点一条线
//第一个点下标为0
double tk = calculate(arr[2], arr[1]);
bool f = false;
int i;
for (i = 2; i < len; i++) {
if (tk != calculate(arr[i], arr[1]))break;
}
double tk2 = calculate(arr[1], arr[0]);
if (i == len && tk != tk2) {
f = true;
cout << "QWQ\n";
return 0;
}
//2.第一个点不孤立，其余点一条线
for (i = 1; i < len; i++) {
//第一个循环遍历与第一个点在同一条直线的点
double k1 = calculate(arr[i], arr[0]);//第一条线的斜率
double k2;
po* p1 = NULL;//指针p指向第一个不在第一条直线上的点
po* p2 = NULL;//指向第二个不在第一条线上的点
int j;
for (j = 1; j < len; j++) {
tk = calculate(arr[j], arr[0]);
if (tk != k1) {
//斜率不同说明不在第一条线
if (p1 == NULL) {
p1 = &arr[j];
}
else if (p2 == NULL) {
p2 = &arr[j];
k2 = calculate(*p2, *p1);//第二条线的斜率
}
else if (p1 != NULL && p2 != NULL) {
tk = calculate(*p1, arr[j]);//后续不在第一条线上的点与第二条线上第一个点连线的斜率
if (tk != k2) {
//不在第二条线
break;
}
}
}
}
if (p1 == NULL && p2 == NULL) {
continue;
}
if (j == len) {
f = true;
}
if (f)break;
}
cout << (f ? "QWQ" : "QAQ") << "\n";
}
return 0;
}
