結果
| 問題 |
No.947 ABC包囲網
|
| コンテスト | |
| ユーザー |
 zeke
|
| 提出日時 | 2019-12-10 00:46:59 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,660 bytes |
| コンパイル時間 | 1,184 ms |
| コンパイル使用メモリ | 106,012 KB |
| 実行使用メモリ | 286,080 KB |
| 最終ジャッジ日時 | 2024-06-23 10:42:22 |
| 合計ジャッジ時間 | 5,454 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 TLE * 1 -- * 31 |
ソースコード
/*
Author:zeke
pass System Test!
GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
ll(s); \
cin >> (s);
#define Scin(s) \
ll(s); \
cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
if (a < b)
{
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
if (b < a)
{
a = b;
return 1;
}
return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
long long modMult(long long a, long long b, long long m)
{
long long res = 0;
long long exp = a % m;
while (b)
{
if (b & 1)
{
res += exp;
if (res > m)
res -= m;
}
exp <<= 1;
if (exp > m)
exp -= m;
b >>= 1;
}
return res;
}
long long powMod(long long a, long long b, long long m)
{
long long res = 1;
long long exp = a % m;
while (b)
{
if (b & 1)
res = modMult(res, exp, m);
exp = modMult(exp, exp, m);
b >>= 1;
}
return res;
}
//powMod(a,b,MOD)
//O(log(b))?
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
ll(s); \
cin >> (s);
#define Scin(s) \
ll(s); \
cin >> (s);
/*template <class T>
bool chmax(T &a, const T &b)
{
if (a < b)
{
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
if (b < a)
{
a = b;
return 1;
}
return 0;
}*/
const double EPS = 1e-20;
double add(double l, double r)
{
if (abs(l + r) < EPS * (abs(l) + abs(r)))
return 0;
return l + r;
}
//l-r は add(l,-r)
//l==r は add(l,-r)==0
struct Pt
{
double x, y;
Pt(double xx = 0, double yy = 0)
{
x = xx;
y = yy;
}
Pt &operator=(const Pt &rhs)
{
x = rhs.x;
y = rhs.y;
return *this;
}
Pt &operator+=(const Pt &rhs)
{
x = add(x, rhs.x);
y = add(y, rhs.y);
return *this;
}
Pt &operator-=(const Pt &rhs)
{
x = add(x, -rhs.x);
y = add(y, -rhs.y);
return *this;
}
Pt &operator*=(const double &rhs)
{
x *= rhs;
y *= rhs;
return *this;
}
Pt &operator/=(const double &rhs)
{
x /= rhs;
y /= rhs;
return *this;
}
};
Pt operator+(const Pt &a) { return a; }
Pt operator-(const Pt &a) { return Pt(-a.x, -a.y); }
Pt operator+(const Pt &lhs, const Pt &rhs)
{
Pt ans = lhs;
ans += rhs;
return ans;
}
Pt operator-(const Pt &lhs, const Pt &rhs)
{
Pt ans = lhs;
ans -= rhs;
return ans;
}
Pt operator*(const Pt &lhs, const double &rhs)
{
Pt ans = lhs;
ans *= rhs;
return ans;
}
Pt operator*(const double &lhs, const Pt &rhs)
{
Pt ans = rhs;
ans *= lhs;
return ans;
}
Pt operator/(const Pt &lhs, const double &rhs)
{
Pt ans = lhs;
ans /= rhs;
return ans;
}
bool operator==(const Pt &lhs, const Pt &rhs)
{
return add(lhs.x, -rhs.x) == 0 && add(lhs.y, -rhs.y) == 0;
}
bool operator!=(const Pt &lhs, const Pt &rhs) { return !(lhs == rhs); }
bool operator<(const Pt &lhs, const Pt &rhs)
{
return add(lhs.x, -rhs.x) != 0 ? lhs.x < rhs.x : add(lhs.y, -rhs.y) < 0;
}
bool operator>(const Pt &lhs, const Pt &rhs) { return rhs < lhs; }
bool operator<=(const Pt &lhs, const Pt &rhs) { return !(lhs > rhs); }
bool operator>=(const Pt &lhs, const Pt &rhs) { return !(lhs < rhs); }
istream &operator>>(istream &is, Pt &rhs)
{
double x, y;
is >> x >> y;
rhs = Pt(x, y);
return is;
}
ostream &operator<<(ostream &os, const Pt &rhs)
{
os << rhs.x << " " << rhs.y;
return os;
}
double norm(const Pt &a) { return add(a.x * a.x, a.y * a.y); }
double abs(const Pt &a) { return sqrt(norm(a)); }
double dot(Pt a, Pt b) { return add(a.x * b.x, a.y * b.y); }
double cross(Pt a, Pt b) { return add(a.x * b.y, -a.y * b.x); }
int ccw(Pt a, Pt b, Pt c)
{
b -= a;
c -= a;
if (cross(b, c) > 0)
return +2; // counter clockwise
if (cross(b, c) < 0)
return -2; // clockwise
if (dot(b, c) < 0)
return +1; // c--a--b on line
if (norm(c) < norm(b))
return -1; // b--c--a on line
return 0; // a--b--c on line
}
//主に幾何問題に使うとよいです
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
ll n;
cin>>n;
vector<Pt> vec(n);
Pt k = {0, 0};
rep(i, n) cin >> vec[i];
VV reg(n, V(n));
rep(i,n){
rep(j,n){
reg[i][j] = ccw(k, vec[i], vec[j]);
// cout<<reg[i][j]<<" ";
}
// cout<<endl;
}
VV reg2(n);
VV reg3(n);
rep(i,n){
rep(j,n){
if(reg[i][j]==2){
reg2[i].push_back(j);
}
if (reg[i][j] == -2)
{
reg3[i].push_back(j);
}
}
}
ll res = 0;
rep(i,n){
rep(j,reg2[i].size()){
rep(k,reg3[i].size()){
if(reg[reg2[i][j]][reg3[i][k]]==2){
res++;
}
}
}
}
cout << res/3 << endl;
}