QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307021 | #7906. Almost Convex | icesmoke | TL | 0ms | 3840kb | C++14 | 5.7kb | 2024-01-17 19:59:19 | 2024-01-17 19:59:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fs first
#define sc second
class BigInteger {
private:
std::vector<int> digits;
bool isNegative;
public:
BigInteger() : isNegative(false) {}
BigInteger(const std::string &num) {
if (num[0] == '-') {
isNegative = true;
for (int i = num.size() - 1; i > 0; --i) {
digits.push_back(num[i] - '0');
}
} else {
isNegative = false;
for (int i = num.size() - 1; i >= 0; --i) {
digits.push_back(num[i] - '0');
}
}
}
BigInteger(__int128 num) {
if (num < 0) {
isNegative = true;
num = -num;
} else {
isNegative = false;
}
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
BigInteger operator+(const BigInteger &other) const {
BigInteger result;
int carry = 0;
int maxSize = std::max(digits.size(), other.digits.size());
for (int i = 0; i < maxSize || carry; ++i) {
if (i == result.digits.size()) {
result.digits.push_back(0);
}
int sum = carry;
if (i < digits.size()) {
sum += digits[i];
}
if (i < other.digits.size()) {
sum += other.digits[i];
}
result.digits[i] = sum % 10;
carry = sum / 10;
}
return result;
}
BigInteger operator*(const BigInteger &other) const {
BigInteger result;
result.digits.resize(digits.size() + other.digits.size(), 0);
for (size_t i = 0; i < digits.size(); ++i) {
int carry = 0;
for (size_t j = 0; j < other.digits.size() || carry; ++j) {
long long sum = result.digits[i + j] + digits[i] * 1LL * (j < other.digits.size() ? other.digits[j] : 0) + carry;
result.digits[i + j] = sum % 10;
carry = sum / 10;
}
}
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
result.isNegative = isNegative ^ other.isNegative;
return result;
}
// 大小判断的重载
bool operator>(const BigInteger &other) const {
if (isNegative != other.isNegative) {
return other.isNegative;
}
if (digits.size() != other.digits.size()) {
return (digits.size() > other.digits.size()) ^ isNegative;
}
for (int i = digits.size() - 1; i >= 0; --i) {
if (digits[i] != other.digits[i]) {
return (digits[i] > other.digits[i]) ^ isNegative;
}
}
return false;
}
// 打印大整数
void print() const {
if (isNegative) {
std::cout << '-';
}
for (int i = digits.size() - 1; i >= 0; --i) {
std::cout << digits[i];
}
std::cout << std::endl;
}
};
struct point{
int x,y;
};
bool cmp(point p1,point p2)
{
if(p1.x!=p2.x) return p1.x<p2.x;
return p1.y<p2.y;
}
__int128 gcd(__int128 a,__int128 b)
{
return b?gcd(b,a%b):a;
}
struct frac{
__int128 x,y;
frac(__int128 x1,__int128 y1){
__int128 x1i = x1*(x1>=0?1:-1);
__int128 y1i = y1*(y1>=0?1:-1);
__int128 g = gcd(x1i,y1i);
x = x1/g,y = y1/g;
}
bool operator<(frac it) const {
BigInteger v1(x),v2(it.y),v3(it.x),v4(y);
return !(v1*v2 > v3*v4);
// return x*it.y < it.x*y;
}
bool operator>(frac it) const {
BigInteger v1(x),v2(it.y),v3(it.x),v4(y);
return v1*v2 > v3*v4;
// return x*it.y > it.x*y;
}
};
frac getAngle(point A,point B,point C)
{
__int128 x1 = B.x - A.x,y1 = B.y - A.y;
__int128 x2 = C.x - A.x,y2 = C.y - A.y;
__int128 up = (x1*x2 + y1*y2)*(x1*x2 + y1*y2);
__int128 down = (x1*x1+y1*y1)*(x2*x2+y2*y2);
return frac(up,down);
}
int check(point a1,point a2,point b)
{
int v1 = (b.y - a2.y)*(a2.x - a1.x);
int v2 = (a2.y - a1.y)*(b.x - a2.x);
if(v1==v2) return 0;
return v1>v2?1:-1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
vector<point>ar(n);
for(int i=0;i<n;i++){
cin>>ar[i].x>>ar[i].y;
}
sort(ar.begin(),ar.end(),cmp);
int m = 0;
vector<int>st(n,0);
vector<pair<point,int>>br;
if(ar.size()<=3){
for(int i=0;i<n;i++){
br.push_back({ar[i],i});
}
}else{
int id = 0;
st[0] = st[1] = 1;
br.push_back({ar[0],0});
for(int i=1;i<n;i++){
while(br.size()>=2 && check(br[br.size()-2].fs,br[br.size()-1].fs,ar[i])<=0){
pair<point,int> t = br.back();
st[t.sc] = 0;
br.pop_back();
}
st[i] = 1;
br.push_back({ar[i],i});
}
m = br.size();
br.push_back({ar[n-2],n-2});
for(int i=n-2;i>=0;i--){
if(st[i]) continue;
while(br.size()>m && check(br[br.size()-2].fs,br[br.size()-1].fs,ar[i])<=0){
pair<point,int> t = br.back();
st[t.sc] = 0;
br.pop_back();
}
st[i] = 1;
br.push_back({ar[i],i});
}
}
m = br.size();
for(auto it:br) st[it.sc] = 1;
int ans = 0;
for(int i=0;i<m;i++){
vector<double>tmp1;
vector<array<frac,2>>tmp;
for(int j=0;j<n;j++){
if(st[j]) continue;
frac v1 = getAngle(br[i].fs,br[(i+1)%m].fs,ar[j]);
frac v2 = getAngle(br[(i+1)%m].fs,br[i].fs,ar[j]);
tmp.push_back({v1,v2});
}
sort(tmp.begin(),tmp.end(),greater<array<frac,2>>());
set<frac>nums;
for(auto it:tmp){
int flag = 1;
if(nums.lower_bound(it[1])!=nums.end()) flag = 0;
nums.insert(it[1]);
ans += flag;
}
}
cout<<ans+1;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...