不知道哪里错了,一直wa
查看原帖
不知道哪里错了,一直wa
819682
Exile_Code楼主2024/1/24 21:13
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>

#define ull             unsigned long long 
#define ll              long long
#define pii             pair<ll ,ll>
#define ft              first
#define sd              second
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,n)       for(ll (i)=0;(i)<(n);(i)++)   
#define forne(i,n)      for(ll (i)=1;(i)<=(n);(i)++)
#define rforn(i,n)      for(ll (i)=(n-1);i>=0;i--)
#define rforne(i,n)     for(ll (i)=n;i>=1;i--)
#define vv              vector
#define inf32           INT32_MAX
#define inf64           INT64_MAX
#define LD              double 
const int N = 4e5 + 100;
const int mod = 998244353;
ll T;



//点类
struct Point {
	LD x, y;
	Point(int x, int y) { this->x = x;	this->y = y; }
	Point() {}
#define line Point 
	//点的加减乘运算
	Point operator+(Point b) { return Point(this->x + b.x, this->y + b.y); }
	Point operator-(Point b) { return Point(this->x - b.x, this->y - b.y); }
	Point operator*(LD t) { return Point(this->x * t, this->y * t); }
	LD operator*(Point b) { return this->x * b.x + this->y * b.y; }
};
class Geomtry_tool {
public:
	//求长度
	static LD len(line a) { return sqrt(a.x * a.x + a.y * a.y); }
	//两个向量求角度,使用的是余弦定理求arccos
	static LD angle(line a, line b) { return acos(a * b / len(a) / len(b)); }
	////两个向量求叉积,
	static LD cross(line a, line b) { return a.x * b.y - a.y * b.x; }
	//epslion,判断是否等于0
	static int sgn(LD x) { LD eps = 1e-8; return x > eps ? 1 : (x < -eps ? -1 : 0); }
	//可以用来判断c在b的左侧还是右侧
	//大于0,c在ab左侧;小于0,c在ab右侧;等于0,三点共线
	static int cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
	//判断直线与线段的交点情况,在同侧则无交点;
	//如果是判断线段与线段有无交点,则需要分别设ab,cd为直线,进行两次判断
	static bool l_S_inter(Point a, Point b, Point c, Point d) {
		return sgn(cross(a, b, c) * cross(a, b, d)) > 0;//直线与线段
	}
	//线段与线段
	static bool S_S_inter(Point a, Point b, Point c, Point d) {
		if (sgn(cross(a, b, c) * cross(a, b, d)) > 0)return false;
		if (sgn(cross(c, d, a) * cross(c, d, b)) > 0)return false;
		return true;
	}
	//求两直线的交点
	Point getNode(Point a, line u, Point b, line v) {
		double t = cross((a - b), v) / cross(v, u);//求面积之比
		return a + u * t;
	}
};
vv<pair<Point, Point>>nums(200020);
vv<int>rs(200020);
void solve() {
	
	int n=1;
	Geomtry_tool fuction;	
	while (n) {
		cin >> n;
		if (!n)	break;
		int cnt = 0;
		forne(i, n)
			cin>>nums[i].first.x>>nums[i].first.y>>nums[i].second.x>>nums[i].second.y;
		forne(i, n) {
			int flag = 0;
			for (int j = i + 1; j <= n; j++)
			{
				if (fuction.S_S_inter(nums[i].first, nums[i].second, nums[j].first, nums[j].second))
				{
					flag = 1;
					break;
				}
			}
			if (!flag) {
				rs[cnt++] = i;
			}
		}
		printf("Top sticks: ");
		for (int i = 0; i < cnt; i++) {
			printf("%d", rs[i]);
			if (i < cnt - 1)
				cout << ", ";
		}
		puts(",");
	}


}
int main() {

	std::ios::sync_with_stdio(false);
	T = 1;
	//cin >> T;

	while (T--)
		solve();


}
2024/1/24 21:13
加载中...